Courcelle's theorem for triangulations

详细信息    查看全文

• 作者：Benjamin A. Burton^a ; ^{bab@maths.uq.edu.au" class="auth_mail" title="E-mail the corresponding author} ; Rodney G. Downey^b ; ^{Rod.Downey@vuw.ac.nz" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Triangulations ; Parameterised complexity ; 3-Manifolds ; Discrete Morse theory ; Turaev&ndash ; Viro invariants
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：146
• 期：Complete
• 页码：264-294
• 全文大小：770 K

文摘

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.