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.

Categories: cs.LO cs.CC cs.DM cs.FL

CMSO-transducing tree-like graph decompositions