Mikołaj Bojańczyk

July 6, 2016

Mikołaj Bojańczyk, Michal Pilipczuk

*Definability equals recognizability for graphs of bounded treewidth.*LICS, 2016 PDFMikołaj Bojańczyk, Michal Pilipczuk

*Optimizing tree decompositions in MSO.*CoRR, 2017 PDF

In paper [1] (see also the arxiv version and these slides) we show that for every there is an MSO transduction, which inputs a graph of tree width at most , and outputs a tree decomposition of width at most . The transduction is nondeterministic, which means it might output several possible tree decompositions, but at least one. A corollary of this result is that a conjecture of Courcelle is true: for languages of graphs of bounded tree width, definability in MSO is equivalent to recognisability.

In paper [2], accepted to STACS 2017, we show that for every there is an MSO transduction which inputs a width tree decomposition and outputs an optimal width tree decomposition of the same graph. Combining these two results, we see that for every there is an MSO transduction which maps graphs of trewidth to their optimal width tree decompositions.

## Leave a Reply