Computational Complexity of the Interleaving Distance

Håvard Bakke Bjerkevik, Magnus Bakke Botnan

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publication34th International Symposium on Computational Geometry (SoCG 2018)
EditorsCsaba D. Toth, Bettina Speckmann
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Chapter13
Pages1-15
Number of pages15
ISBN (Electronic)9783959770668
DOIs
Publication statusPublished - 1 Jun 2018
Externally publishedYes
Event34th International Symposium on Computational Geometry (SoCG 2018) - Budapest, Hungary
Duration: 11 Jun 201814 Jun 2018
Conference number: 34

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume99
ISSN (Print)1868-8969

Conference

Conference34th International Symposium on Computational Geometry (SoCG 2018)
Abbreviated titleSoCG 2018
Country/TerritoryHungary
CityBudapest
Period11/06/1814/06/18

Keywords

  • Interleavings
  • NP-hard
  • Persistent homology

Fingerprint

Dive into the research topics of 'Computational Complexity of the Interleaving Distance'. Together they form a unique fingerprint.

Cite this