Document Open Access Logo

Computational Complexity of the Interleaving Distance

Authors Håvard Bakke Bjerkevik, Magnus Bakke Botnan

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.13.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Håvard Bakke Bjerkevik
Magnus Bakke Botnan

Cite As Get BibTex

Håvard Bakke Bjerkevik and Magnus Bakke Botnan. Computational Complexity of the Interleaving Distance. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.13

Abstract

The interleaving distance is arguably the most prominent distance measure in topological data analysis. In this paper, we provide bounds on the computational complexity of determining the interleaving distance in several settings. We show that the interleaving distance is NP-hard to compute for persistence modules valued in the category of vector spaces. In the specific setting of multidimensional persistent homology we show that the problem is at least as hard as a matrix invertibility problem. Furthermore, this allows us to conclude that the interleaving distance of interval decomposable modules depends on the characteristic of the field. Persistence modules valued in the category of sets are also studied. As a corollary, we obtain that the isomorphism problem for Reeb graphs is graph isomorphism complete.

Subject Classification

Keywords
  • Persistent Homology
  • Interleavings
  • NP-hard

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. In International Symposium on Algorithms and Computation, pages 529-540. Springer, 2015. Google Scholar
  2. Gorô Azumaya. Corrections and supplementaries to my paper concerning Krull-Remak-Schmidt’s theorem. Nagoya Mathematical Journal, 1:117-124, 1950. Google Scholar
  3. Michael Barot. Introduction to the representation theory of algebras. Springer, 2014. Google Scholar
  4. Ulrich Bauer and Michael Lesnick. Induced matchings and the algebraic stability of persistence barcodes. Journal of Computational Geometry, 6(2):162-191, 2015. Google Scholar
  5. Silvia Biasotti, Andrea Cerri, Patrizio Frosini, Daniela Giorgi, and Claudia Landi. Multidimensional size functions for shape comparison. Journal of Mathematical Imaging and Vision, 32(2):161-179, 2008. Google Scholar
  6. Håvard Bakke Bjerkevik. Stability of higher-dimensional interval decomposable persistence modules. arXiv preprint arXiv:1609.02086, 2016. Google Scholar
  7. Håvard Bakke Bjerkevik and Magnus Bakke Botnan. Computational complexity of the interleaving distance. arXiv preprint arXiv:1712.04281, 2017. Google Scholar
  8. Magnus Bakke Botnan. Interval decomposition of infinite zigzag persistence modules. Proceedings of the American Mathematical Society, 145(8):3571–-3577, 2017. Google Scholar
  9. Magnus Bakke Botnan and Michael Lesnick. Algebraic stability of zigzag persistence modules. arXiv preprint arXiv:1604.00655, 2016. Google Scholar
  10. Peter A Brooksbank and Eugene M Luks. Testing isomorphism of modules. Journal of Algebra, 320(11):4020-4029, 2008. Google Scholar
  11. Peter Bubenik, Vin de Silva, and Vidit Nanda. Higher interpolation and extension for persistence modules. SIAM Journal on Applied Algebra and Geometry, 1(1):272-284, 2017. Google Scholar
  12. Peter Bubenik, Vin de Silva, and Jonathan Scott. Metrics for generalized persistence modules. Foundations of Computational Mathematics, 15(6):1501-1531, 2015. Google Scholar
  13. Peter Bubenik and Jonathan A Scott. Categorification of persistent homology. Discrete &Computational Geometry, 51(3):600-627, 2014. Google Scholar
  14. G. Carlsson and A. Zomorodian. The theory of multidimensional persistence. Discrete &Computational Geometry, 42(1):71-93, 2009. Google Scholar
  15. Gunnar Carlsson and Vin de Silva. Zigzag persistence. Foundations of computational mathematics, 10(4):367-405, 2010. Google Scholar
  16. Gunnar Carlsson, Vin de Silva, and Dmitriy Morozov. Zigzag persistent homology and real-valued functions. In Proceedings of the twenty-fifth annual symposium on Computational geometry, pages 247-256. ACM, 2009. Google Scholar
  17. Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas J Guibas, and Steve Y Oudot. Proximity of persistence modules and their diagrams. In Proceedings of the twenty-fifth annual symposium on Computational geometry, pages 237-246. ACM, 2009. Google Scholar
  18. Jérémy Cochoy and Steve Oudot. Decomposition of exact pfd persistence bimodules. arXiv preprint arXiv:1605.09726, 2016. Google Scholar
  19. William Crawley-Boevey. Decomposition of pointwise finite-dimensional persistence modules. Journal of Algebra and Its Applications, 14(05):1550066, 2015. Google Scholar
  20. Vin de Silva, Elizabeth Munch, and Amit Patel. Categorified Reeb graphs. arXiv preprint arXiv:1501.04147, 2015. Google Scholar
  21. Tamal K Dey and Cheng Xin. Computing bottleneck distance for 2-d interval decomposable modules. arXiv preprint arXiv:1803.02869, 2018. Google Scholar
  22. Michael Kerber, Dmitriy Morozov, and Arnur Nigmetov. Geometry helps to compare persistence diagrams. Journal of Experimental Algorithmics (JEA), 22(1):1-4, 2017. Google Scholar
  23. Michael Lesnick. Multidimensional interleavings and applications to topological inference. arXiv preprint arXiv:1206.1365, 2012. Google Scholar
  24. Michael Lesnick. The theory of the interleaving distance on multidimensional persistence modules. Foundations of Computational Mathematics, 15(3):613-650, 2015. Google Scholar
  25. Nikola Milosavljević, Dmitriy Morozov, and Primoz Skraba. Zigzag persistent homology in matrix multiplication time. In Proceedings of the twenty-seventh annual symposium on Computational geometry, pages 216-225. ACM, 2011. Google Scholar
  26. Martina Scolamiero, Wojciech Chachólski, Anders Lundman, Ryan Ramanujam, and Sebastian Öberg. Multidimensional persistence and noise. Foundations of Computational Mathematics, 17(6):1367-1406, 2017. Google Scholar
  27. Cary Webb. Decomposition of graded modules. Proceedings of the American Mathematical Society, 94(4):565-571, 1985. 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 About DROPS Imprint Privacy Contact