CMSO-transducing tree-like graph decompositions

Abstract

We give $\mathrm{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 $\mathrm{MSO}$, a strictly more expressive logic than $\mathrm{CMSO}$. Our methods more generally yield $C_2\mathrm{MSO}$-transductions that output the canonical decompositions of weakly-partitive set systems and weakly-bipartitive systems of bipartitions.