Optimizing tree decompositions in MSO

The classic algorithm of Bodlaender and Kloks [J. Algorithms, 1996] solvesthe following problem in linear fixed-parameter time: given a treedecomposition of a graph of (possibly suboptimal) width k, compute anoptimum-width tree decomposition of the graph. In this work, we prove that thisproblem can also be solved in mso in the following sense: for every positiveinteger k, there is an mso transduction from tree decompositions of width k totree decompositions of optimum width. Together with our recent results [LICS2016], this implies that for every k there exists an mso transduction whichinputs a graph of treewidth k, and nondeterministically outputs its treedecomposition of optimum width. We also show that mso transductions can beimplemented in linear fixed-parameter time, which enables us to derive thealgorithmic result of Bodlaender and Kloks as a corollary of our main result