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 exact pfd persistence bimodules
- Decomposition of Graded Modules
- 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
(22)- On the stability of interval decomposable persistence modules
- A brief introduction to multidimensional persistent Betti numbers
- Generalized persistence algorithm for decomposing multiparameter persistence modules
- Tree decomposition of Reeb graphs, parametrized complexity, and applications to phylogenetics
- Computing the interleaving distance is NP-hard
- Spatiotemporal persistent homology for dynamic metric spaces
- On the geometrical properties of the coherent matching distance in 2D persistent homology
- Topological spaces of persistence modules and their properties
- The theory of the interleaving distance on multidimensional persistence modules
- Relative interleavings and applications to sensor networks
- Multiparameter Persistence Landscapes
- Computational complexity of the interleaving distance
- Computing bottleneck distance for 2-D interval decomposable modules
- Analysis of dynamic graphs and dynamic metric spaces via zigzag persistence
- scientific article; zbMATH DE number 6026956 (Why is no real title available?)
- Computing minimal presentations and bigraded Betti numbers of 2-parameter persistent homology
- Interleaving by parts: join decompositions of interleavings and join-assemblage of geodesics
- Labeled interleaving distance for Reeb graphs
- Bounding the interleaving distance for mapper graphs with a loss function
- A family of metrics from the truncated smoothing of Reeb graphs
- Stabilizing decomposition of multiparameter persistence modules
- Metrics for generalized persistence modules
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)
