TY - JOUR

T1 - Computing the Interleaving Distance is NP-Hard

AU - Bjerkevik, Håvard Bakke

AU - Botnan, Magnus Bakke

AU - Kerber, Michael

PY - 2020/10/1

Y1 - 2020/10/1

N2 - 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.

AB - 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.

KW - Interleavings

KW - Matrix completion problems

KW - NP-hardness

KW - Persistent homology

UR - http://www.scopus.com/inward/record.url?scp=85075147061&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075147061&partnerID=8YFLogxK

U2 - 10.1007/s10208-019-09442-y

DO - 10.1007/s10208-019-09442-y

M3 - Article

AN - SCOPUS:85075147061

VL - 20

SP - 1237

EP - 1271

JO - Foundations of Computational Mathematics

JF - Foundations of Computational Mathematics

SN - 1615-3375

IS - 5

ER -