Computing the interleaving distance is NP-hard (Q2216251)

Multi-dimensional persistence modules are getting important in many applications. However, the computation of the interleaving distance between multi-dimensional persistence modules is considered to be hard, in contrast to the 1-dimensional case, where the computation is equivalent to that of the bottleneck distance by the isometry theorem. In this paper, the authors show that computing the interleaving distance between two 2-dimensional persistence modules is NP-hard. The computation was proved to be CI-hard [\textit{H. B. Bjerkevik} and \textit{M. B. Botnan}, LIPIcs -- Leibniz Int. Proc. Inform. 99, Article 13, 15 p. (2018; Zbl 1489.68103)]. The authors obtain the theorem by showing that CI is NP-complete. Moreover, they also prove the NP-completeness of computing the interleaving distance of two indecomposable persistence modules in the 2-dimensional setting. They also improve the reduction that asserts the CI-hardness of the interleaving distance, showing that a \((3-\varepsilon)\)-approximation of the interleaving distance is NP-hard to obtain for any \(\varepsilon>0\). Another interesting result is that it is NP-complete to decide if there exists a surjection from one persistence module to another.