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

DOI10.1137/18M1168704zbMATH Open1432.57051OpenAlexW2982430530WikidataQ126867586 ScholiaQ126867586MaRDI QIDQ5241237FDOQ5241237

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

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 \(\mathbb R^d\)
• scientific article; zbMATH DE number 7051255

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)

Cites Work

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

Cited In (4)

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

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)