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

DOI10.4230/LIPICS.STACS.2017.18MaRDI QIDQ4636616zbMATH OpenFDO

Authors S. Cabello, Stefan Kratsch, William Pettersson, Benjamin A. Burton

Publication date 19 April 2018

Full work available at URL https://arxiv.org/abs/1802.07175

zbMATH Keywords

computational topologysimplicial complexparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Simplicial sets and complexes in algebraic topology (55U10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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

Recommendations

• The parameterized complexity of finding a 2-sphere in a simplicial complex
• Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete
• A computationally intractable problem on simplicial complexes
• Hardness of embedding simplicial complexes in R^d

Cited in

(4)

• Parametrized complexity of expansion height
• The parameterized complexity of finding a 2-sphere in a simplicial complex
• The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds
• ETH-tight algorithms for finding surfaces in simplicial complexes of bounded treewidth

This page was built for publication: The parameterized complexity of finding a 2-sphere in a simplicial complex

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636616)