2026-07-24T05:46:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11134 2024-03-06T10:47:31Z ddc:004 open_access

Parametrized Complexity of Expansion Height Bauer, Ulrich Rathod, Abhishek Spreer, Jonathan Simple-homotopy theory simple-homotopy type parametrized complexity theory simplicial complexes (modified) dunce hat 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ulrich Bauer and Abhishek Rathod and Jonathan Spreer 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.13 urn:nbn:de:0030-drops-111346 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.13 eng https://creativecommons.org/licenses/by/3.0/legalcode