{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:17:31Z","timestamp":1774981051191,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,11,11]],"date-time":"2019-11-11T00:00:00Z","timestamp":1573430400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,11,11]],"date-time":"2019-11-11T00:00:00Z","timestamp":1573430400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001833","name":"VU University Amsterdam","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001833","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n<jats:p>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.<\/jats:p>","DOI":"10.1007\/s10208-019-09442-y","type":"journal-article","created":{"date-parts":[[2019,11,11]],"date-time":"2019-11-11T20:02:56Z","timestamp":1573502576000},"page":"1237-1271","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["Computing the Interleaving Distance is NP-Hard"],"prefix":"10.1007","volume":"20","author":[{"given":"H\u00e5vard Bakke","family":"Bjerkevik","sequence":"first","affiliation":[]},{"given":"Magnus Bakke","family":"Botnan","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Kerber","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,11]]},"reference":[{"key":"9442_CR1","doi-asserted-by":"crossref","unstructured":"Bauer, U., Lesnick, M.: Induced matchings of barcodes and the algebraic stability of persistence. In: Proceedings of the thirtieth annual symposium on Computational geometry, p. 355. ACM (2014)","DOI":"10.1145\/2582112.2582168"},{"issue":"1","key":"9442_CR2","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1214\/15-AOAS886","volume":"10","author":"P Bendich","year":"2016","unstructured":"Bendich, P., Marron, J.S., Miller, E., Pieloch, A., Skwerer, S.: Persistent homology analysis of brain artery trees. The annals of applied statistics 10 1, 198\u2013218 (2016)","journal-title":"The annals of applied statistics"},{"key":"9442_CR3","unstructured":"Bjerkevik, H.B.: Stability of higher-dimensional interval decomposable persistence modules. arXiv preprint arXiv:1609.02086 (2016)"},{"key":"9442_CR4","unstructured":"Bjerkevik, H.B., Botnan, M.B.: Computational complexity of the interleaving distance. In: 34th International Symposium on Computational Geometry, SoCG 2018, pp. 13:1\u201313:15 (2018)"},{"key":"9442_CR5","doi-asserted-by":"publisher","first-page":"3133","DOI":"10.2140\/agt.2018.18.3133","volume":"18","author":"MB Botnan","year":"2018","unstructured":"Botnan, M.B., Lesnick, M.: Algebraic stability of zigzag persistence modules. Algebraic & Geometric Topology 18, 3133\u20133204 (2018)","journal-title":"Algebraic & Geometric Topology"},{"issue":"11","key":"9442_CR6","doi-asserted-by":"publisher","first-page":"4020","DOI":"10.1016\/j.jalgebra.2008.07.014","volume":"320","author":"PA Brooksbank","year":"2008","unstructured":"Brooksbank, P.A., Luks, E.M.: Testing isomorphism of modules. Journal of Algebra 320(11), 4020\u20134029 (2008)","journal-title":"Journal of Algebra"},{"key":"9442_CR7","unstructured":"Buchet, M., Escolar, E.G.: Realizations of indecomposable persistence modules of arbitrarily large dimension. In: 34th International Symposium on Computational Geometry, SoCG 2018, pp. 15:1\u201315:13 (2018)"},{"key":"9442_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42545-0","volume-title":"The structure and stability of persistence modules","author":"F Chazal","year":"2016","unstructured":"Chazal, F., De\u00a0Silva, V., Glisse, M., Oudot, S.: The structure and stability of persistence modules. Springer, New York (2016)"},{"issue":"6","key":"9442_CR9","doi-asserted-by":"publisher","first-page":"41:1","DOI":"10.1145\/2535927","volume":"60","author":"F Chazal","year":"2013","unstructured":"Chazal, F., Guibas, L.J., Oudot, S.Y., Skraba, P.: Persistence-based clustering in riemannian manifolds. J. ACM 60(6), 41:1\u201341:38 (2013)","journal-title":"J. ACM"},{"key":"9442_CR10","unstructured":"Dey, T.K., Xin, C.: Computing bottleneck distance for 2-d interval decomposable modules. In: 34th International Symposium on Computational Geometry, SoCG 2018, pp. 32:1\u201332:15 (2018)"},{"key":"9442_CR11","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H., Harer, J.: Computational Topology: An Introduction. American Mathematical Society, Providence, RI, USA (2010)","DOI":"10.1090\/mbk\/069"},{"issue":"8","key":"9442_CR12","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1137\/090781231","volume":"39","author":"G Ivanyos","year":"2010","unstructured":"Ivanyos, G., Karpinski, M., Saxena, N.: Deterministic polynomial time algorithms for matrix completion problems. SIAM journal on computing 39(8), 3736\u20133751 (2010)","journal-title":"SIAM journal on computing"},{"key":"9442_CR13","doi-asserted-by":"crossref","unstructured":"Kerber, M., Nigmetov, A.: Geometry helps to compare persistence diagrams. ACM Journal of Experimental Algorithmics 22 (2017)","DOI":"10.1145\/3064175"},{"issue":"3","key":"9442_CR14","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s10208-015-9255-y","volume":"15","author":"M Lesnick","year":"2015","unstructured":"Lesnick, M.: The theory of the interleaving distance on multidimensional persistence modules. Foundations of Computational Mathematics 15(3), 613\u2013650 (2015)","journal-title":"Foundations of Computational Mathematics"},{"key":"9442_CR15","unstructured":"Lesnick, M., Wright, M.: Interactive visualization of 2-d persistence modules. arXiv preprint arXiv:1512.00180 (2015)"},{"issue":"4","key":"9442_CR16","doi-asserted-by":"publisher","first-page":"4281","DOI":"10.1093\/mnras\/stw2862","volume":"465","author":"P Pranav","year":"2016","unstructured":"Pranav, P., Edelsbrunner, H., van de Weygaert, R., Vegter, G., Kerber, M., Jones, B., Wintraecken, M.: The topology of the cosmic web in terms of persistent betti numbers. Monthly Notices of the Royal Astronomical Society 465(4), 4281\u20134310 (2016)","journal-title":"Monthly Notices of the Royal Astronomical Society"},{"key":"9442_CR17","unstructured":"Reininghaus, J., Huber, S., Bauer, U., Kwitt, R.: A stable multi-scale kernel for topological machine learning. In: IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2015, Boston, MA, USA, June 7\u201312, 2015, pp. 4741\u20134748 (2015)"},{"issue":"1","key":"9442_CR18","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1162\/neco_a_01150","volume":"31","author":"E Rybakken","year":"2019","unstructured":"Rybakken, E., Baas, N., Dunn, B.: Decoding of neural data using cohomological feature extraction. Neural computation 31(1), 68\u201393 (2019)","journal-title":"Neural computation"},{"issue":"6","key":"9442_CR19","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1007\/s10208-016-9323-y","volume":"17","author":"M Scolamiero","year":"2017","unstructured":"Scolamiero, M., Chach\u00f3lski, W., Lundman, A., Ramanujam, R., \u00d6berg, S.: Multidimensional persistence and noise. Foundations of Computational Mathematics 17(6), 1367\u20131406 (2017)","journal-title":"Foundations of Computational Mathematics"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-019-09442-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-019-09442-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-019-09442-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,10]],"date-time":"2020-11-10T00:14:09Z","timestamp":1604967249000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-019-09442-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,11]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["9442"],"URL":"https:\/\/doi.org\/10.1007\/s10208-019-09442-y","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,11]]},"assertion":[{"value":"22 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 August 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}