Computing the interleaving distance is NP-hard

DOI10.1007/S10208-019-09442-YMaRDI QIDQ2216251zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 15 December 2020

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1811.09165

zbMATH Keywords

interleavingsmatrix completion problemsNP-hardnesspersistent homology

Mathematics Subject Classification ID

Matrix completion problems (15A83) Persistent homology and applications, topological data analysis (55N31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We show that computing the interleaving distance between two multi-graded persistence modules is NP-hard. More precisely, we show that deciding whether two modules are $1$-interleaved is NP-complete, already for bigraded, interval decomposable modules. Our proof is based on previous work showing that a constrained matrix invertibility problem can be reduced to the interleaving distance computation of a special type of persistence modules. We show that this matrix invertibility problem is NP-complete. We also give a slight improvement of the above reduction, showing that also the approximation of the interleaving distance is NP-hard for any approximation factor smaller than $3$. Additionally, we obtain corresponding hardness results for the case that the modules are indecomposable, and in the setting of one-sided stability. Furthermore, we show that checking for injections (resp. surjections) between persistence modules is NP-hard. In conjunction with earlier results from computational algebra this gives a complete characterization of the computational complexity of one-sided stability. Lastly, we show that it is in general NP-hard to approximate distances induced by noise systems within a factor of 2.

Review text

Multi-dimensional persistence modules are getting important in many applications. However, the computation of the interleaving distance between multi-dimensional persistence modules is considered to be hard, in contrast to the 1-dimensional case, where the computation is equivalent to that of the bottleneck distance by the isometry theorem. In this paper, the authors show that computing the interleaving distance between two 2-dimensional persistence modules is NP-hard. The computation was proved to be CI-hard [\textit{H. B. Bjerkevik} and \textit{M. B. Botnan}, LIPIcs -- Leibniz Int. Proc. Inform. 99, Article 13, 15 p. (2018; Zbl 1489.68103)]. The authors obtain the theorem by showing that CI is NP-complete. Moreover, they also prove the NP-completeness of computing the interleaving distance of two indecomposable persistence modules in the 2-dimensional setting. They also improve the reduction that asserts the CI-hardness of the interleaving distance, showing that a \((3-\varepsilon)\)-approximation of the interleaving distance is NP-hard to obtain for any \(\varepsilon>0\). Another interesting result is that it is NP-complete to decide if there exists a surjection from one persistence module to another.

Recommendations

• Computing bottleneck distance for 2-D interval decomposable modules
• Computational complexity of the interleaving distance
• Exact computation of the matching distance on 2-parameter persistence modules
• Topological spaces of persistence modules and their properties
• Local versus global distances for zigzag and multi-parameter persistence modules
• Interleavings and matchings as representations
• The theory of the interleaving distance on multidimensional persistence modules
• Algebraic homotopy interleaving distance
• The reflection distance between zigzag persistence modules
• Exact computation of the matching distance on 2-parameter persistence modules

Cites work

• Algebraic stability of zigzag persistence modules
• Computational complexity of the interleaving distance
• Computational topology. An introduction
• Computing bottleneck distance for 2-D interval decomposable modules
• Decoding of neural data using cohomological feature extraction
• Deterministic polynomial time algorithms for matrix completion problems
• Geometry helps to compare persistence diagrams
• Induced matchings of barcodes and the algebraic stability of persistence
• Multidimensional persistence and noise
• Persistence-based clustering in Riemannian manifolds
• Realizations of indecomposable persistence modules of arbitrarily large dimension
• Testing isomorphism of modules.
• The structure and stability of persistence modules
• The theory of the interleaving distance on multidimensional persistence modules

Cited in

(24)

• On the stability of interval decomposable persistence modules
• Generalized persistence algorithm for decomposing multiparameter persistence modules
• Algebraic homotopy interleaving distance
• Spatiotemporal persistent homology for dynamic metric spaces
• On the geometrical properties of the coherent matching distance in 2D persistent homology
• The reflection distance between zigzag persistence modules
• The theory of the interleaving distance on multidimensional persistence modules
• Multiparameter Persistence Landscapes
• Exact computation of the matching distance on 2-parameter persistence modules
• Computational complexity of the interleaving distance
• Computing bottleneck distance for 2-D interval decomposable modules
• Exact computation of the matching distance on 2-parameter persistence modules
• Computing minimal presentations and bigraded Betti numbers of 2-parameter persistent homology
• Thickening of the diagonal and interleaving distance
• Labeled interleaving distance for Reeb graphs
• Interleaving distances, monoidal actions and 2-categories
• Decomposition of zero-dimensional persistence modules via rooted subsets
• Bounding the interleaving distance for mapper graphs with a loss function
• Persistent homotopy groups of metric spaces
• Summand-injectivity of interval covers and monotonicity of interval resolution global dimensions
• Monoidal Rips: stable multiparameter filtrations of directed networks
• A family of metrics from the truncated smoothing of Reeb graphs
• Computing p-presentation distances is hard
• Estimating the persistent homology of \(\mathbb{R}^n\)-valued functions using function-geometric multifiltrations

This page was built for publication: Computing the interleaving distance is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2216251)