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 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.
Original language | English |
---|---|
Pages (from-to) | 1237-1271 |
Number of pages | 35 |
Journal | Foundations of Computational Mathematics |
Volume | 20 |
Issue number | 5 |
Early online date | 11 Nov 2019 |
DOIs | |
Publication status | Published - 1 Oct 2020 |
Funding
We thank the anonymous referees for valuable suggestions, including the connection to noise systems discussed in Sect. 7 . Magnus Bakke Botnan has been partially supported by the DFG Collaborative Research Center SFB/TR 109 “Discretization in Geometry and Dynamics”. Michael Kerber is supported by Austrian Science Fund (FWF) Grant Number P 29984-N35.
Funders | Funder number |
---|---|
Austrian Science Fund | P 29984, P 29984-N35 |
Deutsche Forschungsgemeinschaft | SFB/TR 109 |
Keywords
- Interleavings
- Matrix completion problems
- NP-hardness
- Persistent homology