TY - GEN

T1 - Parametrized complexity of expansion height

AU - Bauer, Ulrich

AU - Rathod, Abhishek

AU - Spreer, Jonathan

N1 - Publisher Copyright:
© Ulrich Bauer, Abhishek Rathod, and Jonathan Spreer.

PY - 2019/9

Y1 - 2019/9

N2 - 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.

AB - 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.

KW - (Modified) dunce hat

KW - Parametrized complexity theory

KW - Simple-homotopy theory

KW - Simple-homotopy type

KW - Simplicial complexes

UR - http://www.scopus.com/inward/record.url?scp=85074866463&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2019.13

DO - 10.4230/LIPIcs.ESA.2019.13

M3 - Conference contribution

AN - SCOPUS:85074866463

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 27th Annual European Symposium on Algorithms, ESA 2019

A2 - Bender, Michael A.

A2 - Svensson, Ola

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 27th Annual European Symposium on Algorithms, ESA 2019

Y2 - 9 September 2019 through 11 September 2019

ER -