Computing $p$-presentation distances is hard

Abstract

Recently, $p$-presentation distances for $p\in [1,\infty ]$ were introduced for merge trees and multiparameter persistence modules as more sensitive variations of the respective interleaving distances ($p=\infty )$. It is well-known that computing the interleaving distance is NP-hard in both cases. We extend this result by showing that computing the $p$-presentation distance is NP-hard for all $p\in [1,\infty )$ for both merge trees and $t$-parameter persistence modules for any $t\ge 2$. Though the details differ, both proofs follow the same novel strategy, suggesting that our approach can be adapted to proving the NP-hardness of other distances based on sums or $p$-norms.

36 pages, 12 figures. Expanded after reviewer feedback