文章基本信息

标题：Optimizing Tree Decompositions in MSO
本地全文：下载
作者：Mikolaj Bojanczyk ; Michal Pilipczuk
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：66
页码：15:1-15:13
DOI：10.4230/LIPIcs.STACS.2017.15
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The classic algorithm of Bodlaender and Kloks solves the following problem in linear fixed-parameter time: given a tree decomposition of a graph of (possibly suboptimal) width k, compute an optimum-width tree decomposition of the graph. In this work, we prove that this problem can also be solved in MSO in the following sense: for every positive integer k, there is an MSO transduction from tree decompositions of width k to tree decompositions of optimum width. Together with our recent results, this implies that for every k there exists an MSO transduction which inputs a graph of treewidth k, and nondeterministically outputs its tree decomposition of optimum width.
关键词：tree decomposition; treewidth; transduction; monadic second-order logic