dc.contributor.author | Bjerkevik, Håvard Bakke | |
dc.contributor.author | Botnan, Magnus Bakke | |
dc.contributor.author | Kerber, Michael | |
dc.date.accessioned | 2020-01-30T13:25:16Z | |
dc.date.available | 2020-01-30T13:25:16Z | |
dc.date.created | 2019-12-12T14:27:43Z | |
dc.date.issued | 2019 | |
dc.identifier.issn | 1615-3375 | |
dc.identifier.uri | http://hdl.handle.net/11250/2638917 | |
dc.description.abstract | 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. | nb_NO |
dc.language.iso | eng | nb_NO |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Computing the Interleaving Distance is NP-Hard | nb_NO |
dc.type | Journal article | nb_NO |
dc.type | Peer reviewed | nb_NO |
dc.description.version | publishedVersion | nb_NO |
dc.source.journal | Foundations of Computational Mathematics | nb_NO |
dc.identifier.doi | 10.1007/s10208-019-09442-y | |
dc.identifier.cristin | 1760120 | |
dc.description.localcode | Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. | nb_NO |
cristin.unitcode | 194,63,15,0 | |
cristin.unitname | Institutt for matematiske fag | |
cristin.ispublished | true | |
cristin.fulltext | postprint | |
cristin.qualitycode | 2 | |