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

DOI10.1137/18M1168704MaRDI QIDQ5241237zbMATH OpenOpenAlexWikidataFDO

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

Publication date 30 October 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/18m1168704

zbMATH Keywords

computational topologysimplicial complexparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topology of complexes (57Q05) Triangulating manifolds (57Q15) 2-dimensional topology (including mapping class groups of surfaces, Teichmüller theory, curve complexes, etc.) (57K20)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 6783459 (Why is no real title available?)
• A Census of Planar Triangulations
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number
• A separator theorem for graphs of bounded genus
• A tight lower bound for planar multiway cut with fixed number of terminals
• Algorithms and complexity for Turaev-Viro invariants
• Annotating simplices with a homology basis and its applications
• Color-coding
• Courcelle's theorem for triangulations
• Efficient algorithms to decide tightness
• Einstein structures: Existence versus uniqueness
• Fixed parameter tractable algorithms in combinatorial topology
• Fundamentals of parameterized complexity
• Hardness results for homology localization
• Irreducible triangulations of surfaces with boundary
• Parameterized algorithms
• Planar graphs, via well-orderly maps and trees
• Sphere recognition lies in NP
• The number of rooted triangular maps on a surface
• The topology of four-dimensional manifolds

Cited in

(5)

• The parameterized complexity of finding minimum bounded chains
• The parameterized complexity of finding a 2-sphere in a simplicial complex
• Parametrized complexity of expansion height
• New constructions related to the polynomial sphere recognition problem
• ETH-tight algorithms for finding surfaces in simplicial complexes of bounded treewidth

Describes a project that uses

Uses Software

• MathOverflow

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