CMSO-transducing tree-like graph decompositions
For researchers in graph theory and logic, this paper improves the logical complexity of computing canonical graph decompositions, but the improvement is incremental over existing work.
The authors provide CMSO-transductions that output modular, split, and bi-join decompositions of graphs, improving on previous results that required the more expressive order-invariant MSO logic. Their methods also yield C2MSO-transductions for canonical decompositions of weakly-partitive and weakly-bipartitive set systems.
We give $\operatorname{CMSO}$-transductions that, given a graph $G$, output its modular decomposition, its split decomposition and its bi-join decomposition. This improves results by Courcelle [Logical Methods in Computer Science, 2006] who gave such transductions using order-invariant $\operatorname{MSO}$, a strictly more expressive logic than $\operatorname{CMSO}$. Our methods more generally yield $\operatorname{C}_2 \operatorname{MSO}$-transductions that output the canonical decompositions of weakly-partitive set systems and weakly-bipartitive systems of bipartitions.