Mikołaj Bojańczyk

MSO on graphs


July 6, 2016
  1. Mikołaj Bojańczyk, Michal Pilipczuk
    Definability equals recognizability for graphs of bounded treewidth. LICS, 2016   PDF

  2. Mikoł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 k there is an MSO transduction, which inputs a graph of tree width at most k, and outputs a tree decomposition of width at most f(k). 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 k there is an MSO transduction which inputs a width k tree decomposition and outputs an optimal width tree decomposition of the same graph. Combining these two results, we see that for every k there is an MSO transduction which maps graphs of trewidth k to their optimal width tree decompositions.

 

Leave a Reply

Your email address will not be published.