Courcelle's theorem for triangulations

DOI10.1016/J.JCTA.2016.10.001zbMATH Open1353.05122arXiv1403.2926OpenAlexW2963396031MaRDI QIDQ346450FDOQ346450

Authors: Rodney G. Downey, Benjamin A. Burton 

Publication date: 29 November 2016

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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.

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

Recommendations

• Logic, graphs, and algorithms
• A Practical Approach to Courcelle's Theorem
• Algorithmic meta theorems for sparse graph classes
• Courcelle's theorem -- a game-theoretic approach
• Algorithmic meta-theorems for restrictions of treewidth

zbMATH Keywords

discrete Morse theorytriangulations3-manifoldsparameterised complexityTuraev-Viro invariants

Mathematics Subject Classification ID

Gromov-Witten invariants, quantum cohomology, Gopakumar-Vafa invariants, Donaldson-Thomas invariants (algebro-geometric aspects) (14N35) Graph theory (05C99) Triangulating manifolds (57Q15)

Cites Work

• Title not available (Why is that?)
• Fundamentals of parameterized complexity
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Which problems have strongly exponential complexity?
• Parametrized complexity theory.
• Seifert fibered spaces in 3-manifolds
• Graph structure and monadic second-order logic. A language-theoretic approach
• Easy problems for tree-decomposable graphs
• State sum invariants of 3-manifolds and quantum \(6j\)-symbols
• Graph minors. II. Algorithmic aspects of tree-width
• Courcelle's theorem -- a game-theoretic approach
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Sparsity. Graphs, structures, and algorithms
• A new decomposition theorem for 3-manifolds
• Algorithmic topology and classification of 3-manifolds
• Taut ideal triangulations of \(3\)-manifolds
• 0-efficient triangulations of 3-manifolds
• Computational topology with Regina: algorithms, heuristics and implementations
• Finite covers of random 3-manifolds
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Monadic second-order evaluations on tree-decomposable graphs
• A user's guide to discrete Morse theory
• Tight lower bounds for certain parameterized NP-hard problems
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• The parametrized complexity of knot polynomials
• Fixed parameter tractable algorithms in combinatorial topology
• STRUCTURES OF SMALL CLOSED NON-ORIENTABLE 3-MANIFOLD TRIANGULATIONS
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing Optimal Morse Matchings
• The complexity of detecting taut angle structures on triangulations
• Veering triangulations admit strict angle structures

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
• Title not available (Why is that?)
• 3-manifold triangulations with small treewidth
• Title not available (Why is that?)
• On the pathwidth of hyperbolic 3-manifolds
• Theorem of Stickelberger-Voronoi
• 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
• Title not available (Why is that?)

Uses Software

• Regina

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)