Parametrized complexity of expansion height

Ulrich Bauer, Abhishek Rathod, Jonathan Spreer

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

3 Scopus citations


Deciding whether two simplicial complexes are homotopy equivalent is a fundamental problem in topology, which is famously undecidable. There exists a combinatorial refinement of this concept, called simple-homotopy equivalence: two simplicial complexes are of the same simple-homotopy type if they can be transformed into each other by a sequence of two basic homotopy equivalences, an elementary collapse and its inverse, an elementary expansion. In this article we consider the following related problem: given a 2-dimensional simplicial complex, is there a simple-homotopy equivalence to a 1-dimensional simplicial complex using at most p expansions? We show that the problem, which we call the erasability expansion height, is W[P]-complete in the natural parameter p.

Original languageEnglish
Title of host publication27th Annual European Symposium on Algorithms, ESA 2019
EditorsMichael A. Bender, Ola Svensson, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771245
StatePublished - Sep 2019
Event27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Germany
Duration: 9 Sep 201911 Sep 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference27th Annual European Symposium on Algorithms, ESA 2019


  • (Modified) dunce hat
  • Parametrized complexity theory
  • Simple-homotopy theory
  • Simple-homotopy type
  • Simplicial complexes


Dive into the research topics of 'Parametrized complexity of expansion height'. Together they form a unique fingerprint.

Cite this