2014/03/12 by Benjamin A. Burton, Burton, Benjamin A., Rodney G. Downey +1 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Geometric Topology (math.GT) #cs.CC #cs.CG #math.CO #math.GT
paper · pdf · doi:10.48550/arxiv.1403.2926
24 pages, 7 figures
arxiv created 2014/03/12 · arxiv updated 2014/03/13
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.