The parameterized complexity of finding a 2-sphere in a simplicial complex

Burton, Benjamin, Cabello, Sergio, Kratsch, Stefan and Pettersson, William (2017). The parameterized complexity of finding a 2-sphere in a simplicial complex. In: Heribert Vollmer and Brigitte Vallée, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017. 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, Hannover, Germany, (). 8 - 11 March 2017. doi:10.4230/LIPIcs.STACS.2017.18


Author Burton, Benjamin
Cabello, Sergio
Kratsch, Stefan
Pettersson, William
Title of paper The parameterized complexity of finding a 2-sphere in a simplicial complex
Conference name 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017
Conference location Hannover, Germany
Conference dates 8 - 11 March 2017
Proceedings title 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017   Check publisher's open access policy
Journal name Leibniz International Proceedings in Informatics   Check publisher's open access policy
Place of Publication Wadern, Germany
Publisher Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH
Publication Year 2017
Sub-type Fully published paper
DOI 10.4230/LIPIcs.STACS.2017.18
Open Access Status DOI
ISBN 9783959770286
ISSN 1868-8969
Editor Heribert Vollmer
Brigitte Vallée
Volume 66
Total pages 14
Language eng
Formatted Abstract/Summary
We consider the problem of finding a subcomplex K′ of a simplicial complex K such that K′ is homeomorphic to the 2-dimensional sphere, S2. 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(no(√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(3kpoly(|K|)) time algorithm, and we show that it admits a polynomial kernelization to O(k2) triangles, as well as a polynomial compression to a weighted version with bit-size O(log k).
Keyword Computational topology
Parameterized complexity
Simplicial complex
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Conference Paper
Collections: School of Mathematics and Physics
HERDC Pre-Audit
 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Tue, 11 Apr 2017, 00:25:16 EST by Web Cron on behalf of Learning and Research Services (UQ Library)