Document Open Access Logo

FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees

Authors Elena Farahbakhsh Touli, Yusu Wang

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.83.pdf
  • Filesize: 0.82 MB
  • 14 pages

Document Identifiers

Author Details

Elena Farahbakhsh Touli
  • Stockholm University, Sweden
Yusu Wang
  • The Ohio State University, USA

Funding

This work is partially supported by National Science Foundation (NSF) under grants CCF-1740761, IIS-1815697 and CCF-1618247, as well as by National Institute of Health (NIH) under grant R01EB022899.

Acknowledgements

We thank reviewers for helpful comments. We would like to thank Kyle Fox, for suggesting an elegant double-binary search procedure, to improve the time complexity of the optimal interleaving distance by almost a factor of n^2 (see Theorem 12), which further leads to a similar improvement for approximating the Gromov-Hausdorff distance (Theorem 13).

Cite AsGet BibTex

Elena Farahbakhsh Touli and Yusu Wang. FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 83:1-83:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.83

Abstract

The Gromov-Hausdorff distance is a natural way to measure the distortion between two metric spaces. However, there has been only limited algorithmic development to compute or approximate this distance. We focus on computing the Gromov-Hausdorff distance between two metric trees. Roughly speaking, a metric tree is a metric space that can be realized by the shortest path metric on a tree. Any finite tree with positive edge weight can be viewed as a metric tree where the weight is treated as edge length and the metric is the induced shortest path metric in the tree. Previously, Agarwal et al. showed that even for trees with unit edge length, it is NP-hard to approximate the Gromov-Hausdorff distance between them within a factor of 3. In this paper, we present a fixed-parameter tractable (FPT) algorithm that can approximate the Gromov-Hausdorff distance between two general metric trees within a multiplicative factor of 14. Interestingly, the development of our algorithm is made possible by a connection between the Gromov-Hausdorff distance for metric trees and the interleaving distance for the so-called merge trees. The merge trees arise in practice naturally as a simple yet meaningful topological summary (it is a variant of the Reeb graphs and contour trees), and are of independent interest. It turns out that an exact or approximation algorithm for the interleaving distance leads to an approximation algorithm for the Gromov-Hausdorff distance. One of the key contributions of our work is that we re-define the interleaving distance in a way that makes it easier to develop dynamic programming approaches to compute it. We then present a fixed-parameter tractable algorithm to compute the interleaving distance between two merge trees exactly, which ultimately leads to an FPT-algorithm to approximate the Gromov-Hausdorff distance between two metric trees. This exact FPT-algorithm to compute the interleaving distance between merge trees is of interest itself, as it is known that it is NP-hard to approximate it within a factor of 3, and previously the best known algorithm has an approximation factor of O(sqrt{n}) even for trees with unit edge length.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Gromov-Hausdorff distance
  • Interleaving distance
  • Merge trees

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Pankaj K. Agarwal, Kyle Fox, Abhinandan Nath, Anastasios Sidiropoulos, and Yusu Wang. Computing the Gromov-Hausdorff Distance for Metric Trees. ACM Trans. Algorithms, 14(2):24:1-24:20, 2018. Google Scholar
  2. Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, and Mikkel Thorup. On the approximability of numerical taxonomy (fitting distances by tree metrics). SIAM Journal on Computing, 28(3):1073-1085, 1998. Google Scholar
  3. Nir Ailon and Moses Charikar. Fitting tree metrics: Hierarchical clustering and phylogeny. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, pages 73-82. IEEE, 2005. Google Scholar
  4. Noga Alon, Mihai Bădoiu, Erik D Demaine, Martin Farach-Colton, MohammadTaghi Hajiaghayi, and Anastasios Sidiropoulos. Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. ACM Transactions on Algorithms (TALG), 4(4):46, 2008. Google Scholar
  5. Ulrich Bauer, Xiaoyin Ge, and Yusu Wang. Measuring Distance between Reeb Graphs. In 30th Annual Sympos. on Comput. Geom., page 464, 2014. Google Scholar
  6. Ulrich Bauer, Claudia Landi, and Facundo Mémoli. The Reeb Graph Edit Distance is Universal. CoRR, abs/1801.01866, 2018. URL: http://arxiv.org/abs/1801.01866.
  7. Silvia Biasotti, Daniela Giorgi, Michela Spagnuolo, and Bianca Falcidieno. Reeb graphs for shape analysis and applications. Theor. Comput. Sci., 392(1-3):5-22, 2008. Google Scholar
  8. Philip Bille. A survey on tree edit distance and related problems. Theor. Comput. Sci., 337(1-3):217-239, June 2005. Google Scholar
  9. Alexander M. Bronstein, Michael M. Bronstein, and Ron Kimmel. Efficient computation of isometry-invariant distances between surfaces. SIAM J. on Sci. Comput., 28(5):1812-1836, 2006. Google Scholar
  10. Mihai Bădoiu, Piotr Indyk, and Anastasios Sidiropoulos. Approximation algorithms for embedding general metrics into trees. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 512-521. Society for Industrial and Applied Mathematics, 2007. Google Scholar
  11. Victor Chepoi, Feodor F Dragan, Ilan Newman, Yuri Rabinovich, and Yann Vaxes. Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs. Discrete & Computational Geometry, 47(1):187-214, 2012. Google Scholar
  12. Vin de Silva, Elizabeth Munch, and Amit Patel. Categorified Reeb Graphs. Discrete & Computational Geometry, 55(4):854-906, June 2016. Google Scholar
  13. Michael Fellows, Fedor Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances A Rosamond, and Saket Saurabh. Parameterized Low-distortion Embeddings-Graph metrics into lines and trees. arXiv preprint, 2008. URL: http://arxiv.org/abs/0804.3028.
  14. Xiaoyin Ge, Issam Safa, Mikhail Belkin, and Yusu Wang. Data Skeletonization via Reeb Graphs. In Proc. 25th Annu. Conf. Neural Information Processing Systems (NIPS), pages 837-845, 2011. Google Scholar
  15. Mikhail Gromov. Metric Structures for Riemannian and Non-Riemannian Spaces. Birkhäuser Basel, 2007. Google Scholar
  16. Alexander Hall and Christos Papadimitriou. Approximating the Distortion. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, volume 3624 of Lecture Notes in Computer Science, pages 111-122. Springer Berlin Heidelberg, 2005. Google Scholar
  17. Franck Hétroy and Dominique Attali. Topological quadrangulations of closed triangulated surfaces using the Reeb graph. Graph. Models, 65(1-3):131-148, 2003. Google Scholar
  18. Tao Jiang, Lusheng Wang, and Kaizhong Zhang. Alignment of Trees - An Alternative to Tree Edit. Theor. Comput. Sci., 143(1):137-148, 1995. URL: https://doi.org/10.1016/0304-3975(95)80029-9.
  19. Facundo Mémoli and Guillermo Sapiro. A Theoretical and Computational Framework for Isometry Invariant Recognition of Point Cloud Data. Found. of Comput. Math., 5(3):313-347, 2005. Google Scholar
  20. Dmitriy Morozov, Kenes Beketayev, and Gunther H. Weber. Interleaving Distance between Merge Trees. In Workshop on Topological Methods in Data Analysis and Visualization: Theory, Algorithms and Applications, 2013. Google Scholar
  21. Facundo Mémoli. Some Properties of Gromov–Hausdorff Distances. Discrete & Computational Geometry, pages 1-25, 2012. 10.1007/s00454-012-9406-8. URL: https://doi.org/10.1007/s00454-012-9406-8.
  22. Felix Schmiedl. Computational Aspects of the Gromov-Hausdorff Distance and its Application in Non-rigid Shape Matching. Discrete & Computational Geometry, 57(4):854-880, June 2017. URL: https://doi.org/10.1007/s00454-017-9889-4.
  23. A. Sidiropoulos, D. Wang, and Y. Wang. Metric embeddings with outliers. In Proc. 28th ACM-SIAM Sympos. Discrete Algorithms (SoDA), pages 670-689, 2017. Google Scholar
  24. Julien Tierny. Reeb graph based 3D shape modeling and applications. PhD thesis, Universite des Sciences et Technologies de Lille, 2008. Google Scholar
  25. Elena Farahbakhsh Touli and Yusu Wang. FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees. CoRR, abs/1811.02425, 2018. URL: http://arxiv.org/abs/1811.02425.
  26. Kaizhong Zhang and Tao Jiang. Some MAX SNP-hard results concerning unordered labeled trees. Information Processing Letters, 49(5):249-254, 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact