首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:Parametrized Complexity of Expansion Height
  • 本地全文:下载
  • 作者:Ulrich Bauer ; Abhishek Rathod ; Jonathan Spreer
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2019
  • 卷号:144
  • 页码:1-15
  • DOI:10.4230/LIPIcs.ESA.2019.13
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:Simple-homotopy theory; simple-homotopy type; parametrized complexity theory; simplicial complexes; (modified) dunce hat
国家哲学社会科学文献中心版权所有