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.*STACS, 2017 PDFMikołaj Bojańczyk

*Two monads for graphs.*CoRR, 2018 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], 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 treewidth to their optimal width tree decompositions.

Paper [3] uses the terminology of monads to describe recognisable languages of graphs. This is meant as an alternative description of Courcelle’s VR and HR recognisable graph classes. The paper also has a new result, namely it is decidable if an CMSO definable languages of graphs (of bounded treewidth) can be defined in MSO (i.e. it is decidable if the counting, which is the C in CMSO, is necessary).

## Leave a Reply