Computational complexity of the interleaving distance
From MaRDI portal
Publication:5115780
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.
Recommendations
- Computing the interleaving distance is NP-hard
- Topological spaces of persistence modules and their properties
- Computing bottleneck distance for 2-D interval decomposable modules
- The theory of the interleaving distance on multidimensional persistence modules
- Exact computation of the matching distance on 2-parameter persistence modules
Cites work
- Algebraic stability of zigzag persistence modules
- Categorification of persistent homology
- Computational complexity of the interleaving distance
- Computing bottleneck distance for 2-D interval decomposable modules
- Corrections and Supplementaries to My Paper concerning Krull-Remak-Schmidt’s Theorem
- Decomposition of Graded Modules
- Decomposition of exact pfd persistence bimodules
- Decomposition of pointwise finite-dimensional persistence modules.
- Geometry helps to compare persistence diagrams
- Higher interpolation and extension for persistence modules
- Induced matchings and the algebraic stability of persistence barcodes
- Interval decomposition of infinite zigzag persistence modules
- Introduction to the representation theory of algebras.
- Metrics for generalized persistence modules
- Multidimensional persistence and noise
- On the stability of interval decomposable persistence modules
- Proximity of persistence modules and their diagrams
- Testing isomorphism of modules.
- The theory of multidimensional persistence
- The theory of the interleaving distance on multidimensional persistence modules
- Zigzag persistence
- Zigzag persistent homology and real-valued functions
- Zigzag persistent homology in matrix multiplication time
Cited in
(19)- Spatiotemporal persistent homology for dynamic metric spaces
- Computational complexity of the interleaving distance
- Computing bottleneck distance for 2-D interval decomposable modules
- Tree decomposition of Reeb graphs, parametrized complexity, and applications to phylogenetics
- Topological spaces of persistence modules and their properties
- Interleaving by parts: join decompositions of interleavings and join-assemblage of geodesics
- Generalized persistence algorithm for decomposing multiparameter persistence modules
- Analysis of dynamic graphs and dynamic metric spaces via zigzag persistence
- Computing minimal presentations and bigraded Betti numbers of 2-parameter persistent homology
- scientific article; zbMATH DE number 6026956 (Why is no real title available?)
- The theory of the interleaving distance on multidimensional persistence modules
- Multiparameter Persistence Landscapes
- A brief introduction to multidimensional persistent Betti numbers
- Computing the interleaving distance is NP-hard
- Relative interleavings and applications to sensor networks
- Metrics for generalized persistence modules
- On the geometrical properties of the coherent matching distance in 2D persistent homology
- On the stability of interval decomposable persistence modules
- Labeled interleaving distance for Reeb graphs
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)
