Title: Optimizing tree decompositions in MSO,
Abstract: The classic algorithm of Bodlaender and Kloks [J. Algorithms, 1996] 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 [LICS
2016], 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. We also show that MSO transductions can be
implemented in linear fixed-parameter time, which enables us to derive the
algorithmic result of Bodlaender and Kloks as a corollary of our main result.