Computing the Interleaving Distance is NP-Hard
- PDF / 711,939 Bytes
- 35 Pages / 439.37 x 666.142 pts Page_size
- 37 Downloads / 230 Views
Computing the Interleaving Distance is NP-Hard Håvard Bakke Bjerkevik1 · Magnus Bakke Botnan2 · Michael Kerber3 Received: 22 November 2018 / Revised: 8 August 2019 / Accepted: 10 September 2019 © The Author(s) 2019
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 in 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 onesided stability. Lastly, we show that it is in general NP-hard to approximate distances induced by noise systems within a factor of 2. Keywords NP-hardness · Persistent homology · Interleavings · Matrix completion problems Mathematics Subject Classification 15A83 · 55U99
Communicated by Herbert Edelsbrunner.
B
Magnus Bakke Botnan [email protected] Håvard Bakke Bjerkevik [email protected] Michael Kerber [email protected]
1
Institutt for matematiske fag, NTNU, 7491 Trondheim, Norway
2
Department of Mathematics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, The Netherlands
3
Institut für Geometrie, TU Graz, 8010 Graz, Austria
123
Foundations of Computational Mathematics
1 Introduction 1.1 Motivation and Problem Statement A persistence module M over Rd is a collection of vector spaces {M p } p∈Rd and linear maps M p→q : M p → Mq whenever p ≤ q, with the property that M p→ p is the identity map and the linear maps are composable in the obvious way. For d = 1, we will talk about single-parameter persistence, and for d ≥ 2, we will use the term multi-parameter persistence. Persistence, particularly in its single-parameter version, has recently gained a lot of attention in applied fields, because one of its instantiations is persistent homology, which studies the evolution of homology groups when varying a real scale parameter. The observation that topological features in real data sets carry important information to analyze and reason about the contained data has given rise to the term topological data analysis (TDA) for this research field, with various connections to application areas, e.g., [2,9,16–18]. A recurring task in TDA is the comparison of two persistence modules. The natural notion in terms of algebra is by i
Data Loading...
