Computing the Interleaving Distance is NP-Hard

Håvard Bakke Bjerkevik, Magnus Bakke Botnan*, Michael Kerber

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

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 languageEnglish
Pages (from-to)1237-1271
Number of pages35
JournalFoundations of Computational Mathematics
Volume20
Issue number5
Early online date11 Nov 2019
DOIs
Publication statusPublished - 1 Oct 2020

Keywords

  • Interleavings
  • Matrix completion problems
  • NP-hardness
  • Persistent homology

Fingerprint

Dive into the research topics of 'Computing the Interleaving Distance is NP-Hard'. Together they form a unique fingerprint.

Cite this