Computational Complexity of the Interleaving Distance
From MaRDI portal
Publication:5115780
DOI10.4230/LIPICS.SOCG.2018.13zbMATH Open1489.68103arXiv1712.04281MaRDI QIDQ5115780FDOQ5115780
Håvard Bakke Bjerkevik, Magnus Bakke Botnan
Publication date: 18 August 2020
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.
Full work available at URL: https://arxiv.org/abs/1712.04281
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Persistent homology and applications, topological data analysis (55N31)
Cites Work
- The theory of multidimensional persistence
- Decomposition of pointwise finite-dimensional persistence modules
- Zigzag persistent homology in matrix multiplication time
- Zigzag persistence
- Categorification of persistent homology
- Computational Complexity of the Interleaving Distance
- Title not available (Why is that?)
- Proximity of persistence modules and their diagrams
- Zigzag persistent homology and real-valued functions
- Metrics for generalized persistence modules
- Corrections and Supplementaries to My Paper concerning Krull-Remak-Schmidt’s Theorem
- Testing isomorphism of modules.
- Multidimensional persistence and noise
- Induced Matchings and the Algebraic Stability of Persistence Barcodes
- The theory of the interleaving distance on multidimensional persistence modules
- Higher Interpolation and Extension for Persistence Modules
- Computing the Gromov-Hausdorff Distance for Metric Trees
- On the stability of interval decomposable persistence modules
- Decomposition of Graded Modules
- Algebraic stability of zigzag persistence modules
- Geometry Helps to Compare Persistence Diagrams
- Interval decomposition of infinite zigzag persistence modules
- Introduction to the Representation Theory of Algebras
- Decomposition of exact pfd persistence bimodules
Cited In (18)
- Computational Complexity of the Interleaving Distance
- Title not available (Why is that?)
- Relative interleavings and applications to sensor networks
- Spatiotemporal persistent homology for dynamic metric spaces
- Title not available (Why is that?)
- The theory of the interleaving distance on multidimensional persistence modules
- Computing the interleaving distance is NP-hard
- Metrics for generalized persistence modules
- Topological spaces of persistence modules and their properties
- Computing Minimal Presentations and Bigraded Betti Numbers of 2-Parameter Persistent Homology
- Multiparameter Persistence Landscapes
- Tree decomposition of Reeb graphs, parametrized complexity, and applications to phylogenetics
- A brief introduction to multidimensional persistent Betti numbers
- On the stability of interval decomposable persistence modules
- On the geometrical properties of the coherent matching distance in 2D persistent homology
- Labeled interleaving distance for Reeb graphs
- Generalized persistence algorithm for decomposing multiparameter persistence modules
- Analysis of Dynamic Graphs and Dynamic Metric Spaces via Zigzag Persistence
This page was built for publication: Computational Complexity of the Interleaving Distance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115780)
