# Computing the interleaving distance is NP-hard

arXiv: https://arxiv.org/abs/1811.09165 · HTML: https://mlsanity.com/paper/1811.09165/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2018.

## Built on by (most cited first, 3 of 3)

- [Learning Transfers: Kan Extensions of Topological Invariants of Learned Representations](https://mlsanity.com/paper/2606.07627/) (2026)
- [COMPLEX: A Closed-Form Certified Embedding of Multiparameter Persistence Modules](https://mlsanity.com/paper/2609.22012/) (2026)
- [The sublevel Flood bifiltration: towards scalable 2-parameter persistent homology](https://mlsanity.com/paper/2610.05441/) (2026)

## Abstract (arXiv)

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.