Computing the Gromov-Hausdorff Distance for Metric Trees

Pankaj K. Agarwal, Kyle Fox, Abhinandan Nath, Anastasios Sidiropoulos, Yusu Wang

Abstract

The Gromov-Hausdorff (GH) distance is a fundamental metric for comparing shapes and metric spaces, but it is notoriously difficult to compute. This paper proves that approximating the GH distance is NP-hard even for simple metric trees—specifically, it is hard to approximate better than a factor of 3. To bridge this computational gap, the authors introduce a novel polynomial-time $O(\sqrt{n})$-approximation algorithm by establishing a theoretical connection between the GH distance and the interleaving distance of merge trees.

Introduction

The Gromov-Hausdorff distance measures the "additive distortion" incurred when mapping points from one metric space to another. Intuitively, it quantifies how close two spaces are to being perfectly isometric. This metric is highly valuable in fields such as computer vision for matching deformable shapes or in data science for analyzing hierarchical clustering.

Despite its utility, computing the GH distance is computationally elusive. For general graphs, the problem is at least as hard as the graph isomorphism problem. This research addresses a natural theoretical question: does the problem become tractable if we restrict the spaces to metric trees (trees where edges have continuous lengths)? While standard tree isomorphism is solvable in polynomial time, finding the optimal continuous mapping between metric trees to minimize distance distortion remains a significant challenge.

Hardness of Approximation

To establish the complexity of the problem, the authors provide a lower bound proof showing that the GH distance is strongly NP-hard to compute. They perform a reduction from the 3-PARTITION problem, a known strongly NP-complete problem, to an intermediate problem called BALANCED-PARTITION, and finally to the GH distance problem between two metric trees.

Tree constructions $T_1$ and $T_2$ used in the NP-hardness reduction.

The reduction demonstrates that no polynomial-time algorithm can approximate the GH distance between two metric trees better than a factor of 3 unless P = NP. This result holds even for trees with unit-length edges, highlighting that the continuous nature of the mapping, rather than edge length variation, drives the complexity.

Bridging Geometry and Topology

A key contribution of this work is the theoretical bridge built between the geometric GH distance and the topological interleaving distance. Interleaving distance is a metric typically used in topological data analysis (TDA) to compare merge trees—structures that track the evolution of topological features (like connected components) as a threshold varies.

Visualization of a merge tree $M_f$ derived from a function $f$ and its level sets.

The authors prove that the GH distance ($d_{GH}$) between two metric trees and the interleaving distance ($\Delta$) of their induced merge trees are constant-factor equivalent: $$\frac{1}{2} d_{GH} \le \Delta \le 14 d_{GH}$$ This equivalence is a major theoretical milestone, as it allows the application of tools from TDA to solve a purely geometric embedding problem.

Approximation Algorithm

Leveraging the connection to interleaving distance, the authors design an $O(n^{7/2} \log n)$ time approximation algorithm. The algorithm uses binary search over a candidate set of distance values $\epsilon$. To verify if a distance $\epsilon$ is feasible, the problem is bifurcated:

  1. Long Edges: For subtrees connected by edges longer than a certain threshold, the algorithm employs an exact bipartite matching approach (using the Hopcroft-Karp algorithm).
  2. Short Edges: For regions with short edges, the algorithm carefully trims and maps subtrees to bound the overall distortion.

For metric trees with unit-length edges, this approach yields a clean $O(\sqrt{n})$-approximation. More generally, it achieves an $O(\min\{n, \sqrt{rn}\})$-approximation, where $r$ is the ratio of the longest to the shortest edge.

Key Insights and Results

  • Complexity of Continuous Mappings: Even though discrete tree isomorphism is easy, the continuous nature of metric trees makes finding optimal mappings NP-hard.
  • Topological Equivalence: The tight relationship between GH distance and interleaving distance provides a new framework for shape comparison.
  • Algorithmic Bounds: The paper establishes a factor-3 lower bound and an $O(\sqrt{n})$ upper bound for the approximation of GH distance on trees.

Conclusion

This research provides the first hardness results and approximation algorithms for the Gromov-Hausdorff distance on metric trees. While a significant gap remains between the factor-3 lower bound and the $O(\sqrt{n})$ upper bound, this work lays the foundational groundwork for future research into efficient algorithms for matching metric spaces under additive distortion. Closing this gap remains a primary open question in the field of computational geometry.

Summary updated

BibTeX
@article{agarwal2015computing,
  author = {Pankaj K. Agarwal and Kyle Fox and Abhinandan Nath and Anastasios Sidiropoulos and Yusu Wang},
  title = {{Computing the Gromov-Hausdorff Distance for Metric Trees}},
  journal = {ACM Trans. Algorithms},
  year = {2015},
  doi = {10.1145/3185466},
}
Figure