Computing p-presentation distances is hard
Håvard Bakke Bjerkevik, Magnus Bakke Botnan
Recently, p-presentation distances for p∈[1,∞] were introduced for merge trees and multiparameter persistence modules as more sensitive variations of the respective interleaving distances (p=∞). 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∈[1,∞) for both merge trees and t-parameter persistence modules for any t≥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.
Computing $p$-presentation distances is hard
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\geq 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.
Håvard Bakke Bjerkevik