Abstract: In graph theory, Courcelle's theorem essentially states that, if an algorithmic problem can be formulated in monadic second-order logic, then it can be solved in linear time for graphs of bounded treewidth. We prove such a metatheorem for a general class of triangulations of arbitrary fixed dimension d, including all triangulated d-manifolds: if an algorithmic problem can be expressed in monadic second-order logic, then it can be solved in linear time for triangulations whose dual graphs have bounded treewidth. We apply our results to 3-manifold topology, a setting with many difficult computational problems but very few parameterised complexity results, and where treewidth has practical relevance as a parameter. Using our metatheorem, we recover and generalise earlier fixed-parameter tractability results on taut angle structures and discrete Morse theory respectively, and prove a new fixed-parameter tractability result for computing the powerful but complex Turaev-Viro invariants on 3-manifolds.
Recommendations
Cites work
- scientific article; zbMATH DE number 4049098 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 1241838 (Why is no real title available?)
- scientific article; zbMATH DE number 1142315 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- 0-efficient triangulations of 3-manifolds
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A new decomposition theorem for 3-manifolds
- A user's guide to discrete Morse theory
- Algorithmic topology and classification of 3-manifolds
- Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
- Computational topology with Regina: algorithms, heuristics and implementations
- Computing Optimal Morse Matchings
- Courcelle's theorem -- a game-theoretic approach
- Easy problems for tree-decomposable graphs
- Finite covers of random 3-manifolds
- Fixed parameter tractable algorithms in combinatorial topology
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fundamentals of parameterized complexity
- Graph minors. II. Algorithmic aspects of tree-width
- Graph structure and monadic second-order logic. A language-theoretic approach
- Monadic second-order evaluations on tree-decomposable graphs
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Parametrized complexity theory.
- STRUCTURES OF SMALL CLOSED NON-ORIENTABLE 3-MANIFOLD TRIANGULATIONS
- Seifert fibered spaces in 3-manifolds
- Sparsity. Graphs, structures, and algorithms
- State sum invariants of 3-manifolds and quantum \(6j\)-symbols
- Taut ideal triangulations of \(3\)-manifolds
- The complexity of detecting taut angle structures on triangulations
- The parametrized complexity of knot polynomials
- Tight lower bounds for certain parameterized NP-hard problems
- Veering triangulations admit strict angle structures
- Which problems have strongly exponential complexity?
Cited in
(15)- Equivalences to the triangulation conjecture
- Treewidth, crushing and hyperbolic volume
- Traversing three-manifold triangulations and spines
- Serrin-type theorems for triangles
- Exposé Bourbaki 1163 : Manolescu's work on the Triangulation Conjecture
- The Milnor-Totaro theorem for space polygons
- scientific article; zbMATH DE number 7236450 (Why is no real title available?)
- scientific article; zbMATH DE number 1553617 (Why is no real title available?)
- 3-manifold triangulations with small treewidth
- Theorem of Stickelberger-Voronoi
- On the pathwidth of hyperbolic 3-manifolds
- The parameterized complexity of finding a 2-sphere in a simplicial complex
- Algorithms and complexity for Turaev-Viro invariants
- Algorithms and complexity for Turaev-Viro invariants
- scientific article; zbMATH DE number 67893 (Why is no real title available?)
This page was built for publication: Courcelle's theorem for triangulations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q346450)
