Computing the Gromov-Hausdorff Distance for Metric Trees

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

Abstract

The Gromov-Hausdorff distance is a natural way to measure distance between two metric spaces. We give the first proof of hardness and first non-trivial approximation algorithm for computing the Gromov-Hausdorff distance for geodesic metrics in trees. Specifically, we prove it is $$\mathrm {NP}$$ -hard to approximate the Gromov-Hausdorff distance better than a factor of 3. We complement this result by providing a polynomial time $$O(\min \{n, \sqrt{rn}\})$$ -approximation algorithm where r is the ratio of the longest edge length in both trees to the shortest edge length. For metric trees with unit length edges, this yields an $$O(\sqrt{n})$$ -approximation algorithm.
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