Abstract
The interleaving distance is arguably the most prominent distance measure in topological data analysis. In this paper, we provide bounds on the computational complexity of determining the interleaving distance in several settings. We show that the interleaving distance is NP-hard to compute for persistence modules valued in the category of vector spaces. In the specific setting of multidimensional persistent homology we show that the problem is at least as hard as a matrix invertibility problem. Furthermore, this allows us to conclude that the interleaving distance of interval decomposable modules depends on the characteristic of the field. Persistence modules valued in the category of sets are also studied. As a corollary, we obtain that the isomorphism problem for Reeb graphs is graph isomorphism complete.
Original language | English |
---|---|
Title of host publication | 34th International Symposium on Computational Geometry (SoCG 2018) |
Editors | Csaba D. Toth, Bettina Speckmann |
Place of Publication | Dagstuhl |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Chapter | 13 |
Pages | 1-15 |
Number of pages | 15 |
ISBN (Electronic) | 9783959770668 |
DOIs | |
Publication status | Published - 1 Jun 2018 |
Externally published | Yes |
Event | 34th International Symposium on Computational Geometry (SoCG 2018) - Budapest, Hungary Duration: 11 Jun 2018 → 14 Jun 2018 Conference number: 34 |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Publisher | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik |
Volume | 99 |
ISSN (Print) | 1868-8969 |
Conference
Conference | 34th International Symposium on Computational Geometry (SoCG 2018) |
---|---|
Abbreviated title | SoCG 2018 |
Country/Territory | Hungary |
City | Budapest |
Period | 11/06/18 → 14/06/18 |
Keywords
- Interleavings
- NP-hard
- Persistent homology