License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.18
URN: urn:nbn:de:0030-drops-70156
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7015/
Go to the corresponding LIPIcs Volume Portal

Burton, Benjamin ; Cabello, Sergio ; Kratsch, Stefan ; Pettersson, William

The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex

pdf-format:
LIPIcs-STACS-2017-18.pdf (0.6 MB)

Abstract

We consider the problem of finding a subcomplex K' of a simplicial complex K such that K' is homeomorphic to the 2-dimensional sphere, S^2. We study two variants of this problem. The first asks if there exists such a K' with at most k triangles, and we show that this variant is W[1]-hard and, assuming ETH, admits no O(n^(o(sqrt(k)))) time algorithm. We also give an algorithm that is tight with regards to this lower bound. The second problem is the dual of the first, and asks if K' can be found by removing at most k triangles from K. This variant has an immediate O(3^k poly(|K|)) time algorithm, and we show that it admits a polynomial kernelization to O(k^2) triangles, as well as a polynomial compression to a weighted version with bit-size O(k log k).

BibTeX - Entry

@InProceedings{burton_et_al:LIPIcs:2017:7015,
  author =	{Benjamin Burton and Sergio Cabello and Stefan Kratsch and William Pettersson},
  title =	{{The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte ValleĢe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7015},
  URN =		{urn:nbn:de:0030-drops-70156},
  doi =		{10.4230/LIPIcs.STACS.2017.18},
  annote =	{Keywords: computational topology, parameterized complexity, simplicial complex}
}

Keywords: computational topology, parameterized complexity, simplicial complex
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI