pith. sign in

arxiv: 2412.04970 · v5 · submitted 2024-12-06 · 💻 cs.LO · cs.CC· cs.DM· cs.FL

CMSO-transducing tree-like graph decompositions

Rutger Campbell , Bruno Guillon , Mamadou Moustapha Kant\'e , Eun Jung Kim , Noleen K\"ohler This is my paper

Pith reviewed 2026-05-23 08:18 UTC · model grok-4.3

classification 💻 cs.LO cs.CCcs.DMcs.FL
keywords CMSO-transductionsmodular decompositionsplit decompositionbi-join decompositionweakly-partitive set systemsgraph decompositionsmonadic second-order logic
0
0 comments X

The pith

CMSO-transductions output a graph's modular decomposition, split decomposition and bi-join decomposition.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that CMSO-transductions suffice to produce the modular decomposition, the split decomposition, and the bi-join decomposition directly from any input graph. Earlier work achieved similar outputs only with the stronger order-invariant MSO. The same construction also supplies C2MSO-transductions for the canonical decompositions of weakly-partitive set systems and weakly-bipartitive systems of bipartitions. A reader would care because these results place complex, tree-like graph decompositions inside a strictly weaker logic than previously known.

Core claim

We give CMSO-transductions that, given a graph G, output its modular decomposition, its split decomposition and its bi-join decomposition. This improves results by Courcelle who gave such transductions using order-invariant MSO, a strictly more expressive logic than CMSO. Our methods more generally yield C2MSO-transductions that output the canonical decompositions of weakly-partitive set systems and weakly-bipartitive systems of bipartitions.

What carries the argument

CMSO-transductions that construct the decomposition structures from the input graph or set system.

If this is right

  • These decompositions become definable without linear orders on the vertices.
  • Algorithms relying on CMSO model-checking can now target the decompositions directly.
  • The same transduction technique applies to decompositions of set systems beyond graphs.
  • Results extend from graphs to weakly-partitive and weakly-bipartitive systems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Other canonical decompositions studied in graph theory may also admit CMSO definitions.
  • Fixed-parameter algorithms for problems on these decompositions could be obtained via existing CMSO machinery.
  • The approach might transfer to related structures such as treewidth or rank-width decompositions.

Load-bearing premise

The canonical decompositions admit definitions inside CMSO or C2MSO that require no ordering of the underlying elements.

What would settle it

Exhibiting one graph whose modular decomposition cannot be produced by any CMSO-transduction from the graph itself.

Figures

Figures reproduced from arXiv: 2412.04970 by Bruno Guillon, Eun Jung Kim, Mamadou Moustapha Kant\'e, Noleen K\"ohler, Rutger Campbell.

Figure 1
Figure 1. Figure 1: Left: A weakly-partitive set system for which strong sets are indicated by red, thick lines and singletons are omitted. Right: The laminar tree obtain by considering the laminar set system consisting of the strong sets. Here the node labeled linear plus the linear ordering of its children indicate that the leaves of every < interval corresponds to a set in the set system (e.g. {a, b, c} is in the set syste… view at source ↗
Figure 2
Figure 2. Figure 2: Left: A weakly-bipartitive system of bipartitions for which strong bipartitions are indicated by red, thick lines and bipartitions of the form {{a}, U \{a}} are omitted. Right: The laminar tree obtain by considering the laminar system of bipartitions consisting of the strong bipartitions. The node labeled linear plus the linear ordering of its children indicate that the leaves of every < interval correspon… view at source ↗
Figure 3
Figure 3. Figure 3: Overview of the various transductions in the paper. An arrow from x to y indicates that result x is used in the proof of result y. amongst the elements of U and a non-deterministic coloring which allows the assignment of representatives to nodes by means of a C2MSO-formula. It should be mentioned that a similar result is claimed in the preprint [Boj23], where a proof sketch designing a C3MSO￾transduction i… view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of a bi-colouring (A, B) identifying some set S ⊆ V \ L in a binary tree T. Leaves from A are blue diamonds, leaves from B are orange filled circles, and inner nodes from S are filled purple squares. Furthermore, the two paths connecting an inner node s ∈ S to its A- and B-representatives are coloured blue and orange, respectively. Nodes labeled x1, x2, x3 constitute examples illustrating the … view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of a partition of the inner nodes into 4 thin sets indicated by different shapes/fillings. The four colourings identifying each thin set are indicated in the table below the leaves where an orange slash indicates the leaf being in the corresponding set A and a blue cross indicates the leaf being in B. The key point of our construction consists in defining a C2MSO-formula reprA,B(a, X) which, a… view at source ↗
Figure 6
Figure 6. Figure 6: Sets to be included in a weakly-partitive set system (excluds the rightmost) or in a partitive set system (includes the rightmost) for two overlapping sets X and Y . Proof of Theorem 3.1. The C2MSO-transduction is obtained by composing the following atomic C2MSO-transductions. The transduction makes use of the formulas reprA,B(a, X) given by Lemma 3.11. (1) Guess a family of four bi-colourings (Ai , Bi)i∈[… view at source ↗
Figure 7
Figure 7. Figure 7: Bipartitions to be included in a weakly-bipartitive system of bipartitions (excluds the rightmost) or in a bipartitive system bipartitions (includes the rightmost) for two overlapping bipartitions {X, Y } and {X′ , Y ′}. 5.1. Transducing weakly-bipartitive trees. A bipartition system is a pair (U, B) consist￾ing of a finite set U, the universe, and a family B of bipartitions of U such that {∅, U} ∈ B / and… view at source ↗
Figure 8
Figure 8. Figure 8: A directed graph G with 3 strong splits (left). The weakly-partitive tree of G (middle) and the split decomposition of G where c-edges are the thin, black edges, t-edges are the fat, dashed, blue edges and the (non-singleton) components of the decomposition are signified by grey circles. • H is a directed graph consisting of the disjoint union of the graphs Gu for every inner node u of T and • F is a symme… view at source ↗
Figure 9
Figure 9. Figure 9: A graph G with three non-trivial strong bi-joins (left), the partitive tree of B G join (middle) and its Skeleton graph (right). Dashed edges are t-edges, squiggly edges are r-edges and the rest are c-edges. Equivalence class vertices are represented by squares apart from the singleton equivalence classes corresponding to vertices of G. Note that the edges of the graph G correspond one-to-one to paths in t… view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper constructs explicit CMSO-transductions that, on input a graph G, produce its modular decomposition, split decomposition, and bi-join decomposition. It further gives C₂MSO-transductions realizing the canonical decompositions of weakly-partitive set systems and weakly-bipartitive systems of bipartitions. These constructions are claimed to operate directly inside the stated logics without order-invariance or external structure, improving on Courcelle (LMCS 2006) who required order-invariant MSO.

Significance. If the explicit constructions hold, the result demonstrates that several canonical graph decompositions are definable by CMSO (respectively C₂MSO) transductions, removing the need for order-invariance. This strengthens the known expressive power of counting monadic second-order logic for structural graph theory and supplies concrete logical characterizations that may be useful for algorithmic meta-theorems and decomposition-based algorithms.

major comments (2)
  1. [§3] §3 (modular decomposition transduction): the construction appears to rely on identifying strong modules via a fixed-point iteration expressed in CMSO; it is not immediately clear from the text whether the iteration is bounded by a CMSO-definable parameter or whether an auxiliary ordering is implicitly used to break ties among equivalent modules.
  2. [§5] §5 (general weakly-partitive case): the reduction from the graph decompositions to the set-system case is stated to be CMSO-expressible, but the proof sketch does not exhibit the precise transduction that maps a graph to its associated set system while preserving the canonical decomposition property.
minor comments (2)
  1. [Introduction] Notation for the output structures (e.g., how the decomposition tree is encoded as a relational structure) is introduced only informally in the introduction and should be formalized once in a dedicated preliminary subsection.
  2. [§4] Several lemmas in §4 are stated without proof sketches; while the overall argument is clear, adding one-sentence justifications would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the recommendation of minor revision. We address the two major comments point by point below.

read point-by-point responses

  1. Referee: [§3] §3 (modular decomposition transduction): the construction appears to rely on identifying strong modules via a fixed-point iteration expressed in CMSO; it is not immediately clear from the text whether the iteration is bounded by a CMSO-definable parameter or whether an auxiliary ordering is implicitly used to break ties among equivalent modules.

    Authors: The fixed-point iteration is expressed directly as the least fixed point of a CMSO-definable monotone operator on the power set of vertices; the operator itself is given by a CMSO formula that, for any pair of vertices, selects the unique minimal strong module containing them. Because this module is canonically determined, no auxiliary ordering is required to resolve ties. The number of iterations is bounded by |V|, which is CMSO-definable via counting quantifiers, so the entire construction stays inside CMSO. We will insert a short clarifying paragraph after the definition of the operator to make the absence of ordering explicit. revision: partial

  2. Referee: [§5] §5 (general weakly-partitive case): the reduction from the graph decompositions to the set-system case is stated to be CMSO-expressible, but the proof sketch does not exhibit the precise transduction that maps a graph to its associated set system while preserving the canonical decomposition property.

    Authors: The reduction is realized by the CMSO transduction whose universe is V(G) and whose set predicate is interpreted by the CMSO formula defining the modules (respectively splits or bi-joins) already constructed in §§3–4. Because the canonical decomposition of a weakly-partitive set system is uniquely determined by the inclusion-minimal members of the family, the same formulas that define the graph decomposition also define the set-system decomposition. We agree that the sketch would benefit from an explicit listing of the two-sorted interpretation; this will be added as a short subsection in the revised §5. revision: yes

Circularity Check

0 steps flagged

No significant circularity; explicit constructions over external reference

full rationale

The paper's central contribution consists of explicit CMSO (and C₂MSO) transduction constructions that directly output the canonical modular, split, bi-join, and weakly-partitive decompositions. These are presented as improvements on Courcelle's 2006 result (an external citation using a strictly stronger logic), with no equations, fitted parameters, self-definitional loops, or load-bearing self-citations appearing in the derivation. The constructions are self-contained within the stated logics and do not reduce to renaming or importing uniqueness from the authors' prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of CMSO-definable transductions for the listed decompositions; the abstract invokes standard background notions of CMSO, transductions, and the cited decompositions without introducing new free parameters or invented entities.

axioms (1)
  • standard math Standard definitions of CMSO, C₂MSO, transductions, modular decomposition, split decomposition, bi-join decomposition, weakly-partitive set systems and weakly-bipartitive systems of bipartitions.
    The paper builds directly on these established concepts from logic and graph theory.

pith-pipeline@v0.9.0 · 5640 in / 1191 out tokens · 22198 ms · 2026-05-23T08:18:12.756176+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    Linear rank-width of distance-hereditary graphs I

    Isolde Adler, Mamadou Moustapha Kant \' e , and O - joung Kwon. Linear rank-width of distance-hereditary graphs I . A polynomial-time algorithm. Algorithmica , 78(1):342--377, 2017

    work page 2017

  2. [2]

    Dragan, Ho \` a ng - Oanh Le, and Raffaele Mosca

    Andreas Brandst \" a dt, Feodor F. Dragan, Ho \` a ng - Oanh Le, and Raffaele Mosca. New graph classes of bounded clique-width. Theory Comput. Syst. , 38(5):623--645, 2005. URL: https://doi.org/10.1007/s00224-004-1154-6, https://doi.org/10.1007/S00224-004-1154-6 doi:10.1007/S00224-004-1154-6

    work page doi:10.1007/s00224-004-1154-6 2005

  3. [3]

    Definable decompositions for graphs of bounded linear cliquewidth

    Mikołaj Bojańczyk, Martin Grohe, and Michał Pilipczuk. Definable decompositions for graphs of bounded linear cliquewidth. Log. Methods Comput. Sci. , 17(1), 2021

    work page 2021

  4. [4]

    A linear time algorithm for finding tree-decompositions of small treewidth

    Hans L Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing , pages 226--234, 1993

    work page 1993

  5. [5]

    The category of mso transductions

    Mikołaj Bojańczyk. The category of mso transductions. may 2023. URL: http://arxiv.org/abs/2305.18039v1, http://arxiv.org/abs/2305.18039v1 arXiv:2305.18039v1

    work page arXiv 2023

  6. [6]

    Definability equals recognizability for graphs of bounded treewidth

    Mikołaj Bojańczyk and Michał Pilipczuk. Definability equals recognizability for graphs of bounded treewidth. In Martin Grohe, Eric Koskinen, and Natarajan Shankar, editors, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016 , pages 407--416. ACM , 2016. https://doi.org/10.1145/293357...

    work page doi:10.1145/2933575.2934508 2016

  7. [7]

    Graph structure and monadic second-order logic, a language theoretic approach, Cambridge University Press, 2012

    Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic . Cambridge University Press, 2012. URL: https://doi.org/10.1017 https://doi.org/10.1017/cbo9780511977619 doi:10.1017/cbo9780511977619

    work page doi:10.1017/cbo9780511977619 2012

  8. [8]

    Cmso-transducing tree-like graph decompositions

    Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kant \' e , Eun Jung Kim, and Noleen K \" o hler. Cmso-transducing tree-like graph decompositions. In Olaf Beyersdorff, Michal Pilipczuk, Elaine Pimentel, and Kim Thang Nguyen, editors, 42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025, March 4-7, 2025, Jena, Germany , vol...

    work page doi:10.4230/lipics.stacs.2025.22 2025

  9. [9]

    Recognisability equals definability for finitely representable matroids of bounded path-width

    Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kant \' e , Eun Jung Kim, and Sang-il Oum. Recognisability equals definability for finitely representable matroids of bounded path-width. In Lars Birkedal and Barbara König, editors, Proceedings of the Fortieth Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, Singapour, Singapour, USA, Jun...

    work page 2025

  10. [10]

    Partitive hypergraphs

    Michel Chein, Michel Habib, and Marie-Catherine Maurer. Partitive hypergraphs. Discrete mathematics , 37(1):35--50, 1981

    work page 1981

  11. [11]

    The monadic second-order logic of graphs

    Bruno Courcelle. The monadic second-order logic of graphs. I . recognizable sets of finite graphs. Information and computation , 85(1):12--75, 1990

    work page 1990

  12. [12]

    The monadic second-order logic of graphs V : On closing the gap between definability and recognizability

    Bruno Courcelle. The monadic second-order logic of graphs V : On closing the gap between definability and recognizability. Theoretical Computer Science , 80(2):153--202, 1991

    work page 1991

  13. [13]

    The monadic second-order logic of graphs X: linear orderings

    Bruno Courcelle. The monadic second-order logic of graphs X: linear orderings. Theor. Comput. Sci. , 160(1 & 2):87--143, 1996. https://doi.org/10.1016/0304-3975(95)00083-6 doi:10.1016/0304-3975(95)00083-6

    work page doi:10.1016/0304-3975(95)00083-6 1996

  14. [14]

    The monadic second-order logic of graphs XI: hierarchical decompositions of connected graphs

    Bruno Courcelle. The monadic second-order logic of graphs XI: hierarchical decompositions of connected graphs. Theor. Comput. Sci. , 224(1-2):35--58, 1999. https://doi.org/10.1016/S0304-3975(98)00306-5 doi:10.1016/S0304-3975(98)00306-5

    work page doi:10.1016/s0304-3975(98)00306-5 1999

  15. [15]

    The monadic second-order logic of graphs XVI : Canonical graph decompositions

    Bruno Courcelle. The monadic second-order logic of graphs XVI : Canonical graph decompositions. Logical Methods in Computer Science , 2, 2006

    work page 2006

  16. [16]

    Canonical graph decompositions

    Bruno Courcelle. Canonical graph decompositions. Talk, 2012. Available at https://www.labri.fr/perso/courcell/Conferences/ExpoCanDecsJuin2012.pdf

    work page 2012

  17. [17]

    The atomic decomposition of strongly connected graphs

    Bruno Courcelle. The atomic decomposition of strongly connected graphs. Technical report, Université de Bordeaux, 2013. Available at https://www.labri.fr/perso/courcell/ArticlesEnCours/AtomicDecSubmitted.pdf

    work page 2013

  18. [18]

    Fully dynamic recognition algorithm and certificate for directed cographs

    Christophe Crespelle and Christophe Paul. Fully dynamic recognition algorithm and certificate for directed cographs. Discret. Appl. Math. , 154(12):1722--1741, 2006. URL: https://doi.org/10.1016/j.dam.2006.03.005, https://doi.org/10.1016/J.DAM.2006.03.005 doi:10.1016/J.DAM.2006.03.005

    work page doi:10.1016/j.dam.2006.03.005 2006

  19. [19]

    Decomposition of directed graphs

    William H Cunningham. Decomposition of directed graphs. SIAM Journal on Algebraic Discrete Methods , 3(2):214--228, 1982

    work page 1982

  20. [20]

    Décomposition modulaire des graphes

    Fabien de Montgolfier. Décomposition modulaire des graphes. Théorie, extension et algorithmes . Phd thesis, Université Montpellier II, LIRMM, 2003

    work page 2003

  21. [21]

    The bi-join decomposition

    Fabien de Montgolfier and Micha \" e l Rao. The bi-join decomposition. Electron. Notes Discret. Math. , 22:173--177, 2005. URL: https://doi.org/10.1016/j.endm.2005.06.039, https://doi.org/10.1016/J.ENDM.2005.06.039 doi:10.1016/J.ENDM.2005.06.039

    work page doi:10.1016/j.endm.2005.06.039 2005

  22. [22]

    The Theory of 2-Structures - A Framework for Decomposition and Transformation of Graphs

    Andrzej Ehrenfeucht, Tero Harju, and Grzegorz Rozenberg. The Theory of 2-Structures - A Framework for Decomposition and Transformation of Graphs . World Scientific, 1999. URL: http://www.worldscibooks.com/mathematics/4197.html

    work page 1999

  23. [23]

    Tree automata and pigeonhole classes of matroids: I

    Daryl Funk, Dillon Mayhew, and Mike Newman. Tree automata and pigeonhole classes of matroids: I . Algorithmica , 84(7):1795--1834, 2022. URL: https://doi.org/10.1007/s00453-022-00939-7, https://doi.org/10.1007/S00453-022-00939-7 doi:10.1007/S00453-022-00939-7

    work page doi:10.1007/s00453-022-00939-7 2022

  24. [24]

    Order-invariant MSO is stronger than counting MSO in the finite

    Tobias Ganzow and Sasha Rubin. Order-invariant MSO is stronger than counting MSO in the finite. In Susanne Albers and Pascal Weil, editors, STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21-23, 2008, Proceedings , volume 1 of LIPIcs , pages 313--324. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Info...

    work page doi:10.4230/lipics.stacs.2008.1353 2008

  25. [25]

    A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs

    Michel Habib, Fabien de Montgolfier, Lalla Mouatadid, and Mengchuan Zou. A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs. Theor. Comput. Sci. , 923:56--73, 2022. URL: https://doi.org/10.1016/j.tcs.2022.04.052, https://doi.org/10.1016/J.TCS.2022.04.052 doi:10.1016/J.TCS.2022.04.052

    work page doi:10.1016/j.tcs.2022.04.052 2022

  26. [26]

    Branch-width, parse trees, and monadic second-order logic for matroids

    Petr Hlinen \' y . Branch-width, parse trees, and monadic second-order logic for matroids. J. Comb. Theory B , 96(3):325--351, 2006. URL: https://doi.org/10.1016/j.jctb.2005.08.005, https://doi.org/10.1016/J.JCTB.2005.08.005 doi:10.1016/J.JCTB.2005.08.005

    work page doi:10.1016/j.jctb.2005.08.005 2006

  27. [27]

    e l Rao. NLC-2 graph recognition and isomorphism. In Andreas Brandst \

    Vincent Limouzy, Fabien de Montgolfier, and Micha \" e l Rao. NLC-2 graph recognition and isomorphism. In Andreas Brandst \" a dt, Dieter Kratsch, and Haiko M \" u ller, editors, Graph-Theoretic Concepts in Computer Science, 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers , volume 4769 of Lecture Notes in Computer...

    work page 2007

  28. [28]

    Décompositions de graphes et algorithmes efficaces

    Michaël Rao. Décompositions de graphes et algorithmes efficaces . Phd thesis, Université Paul Verlaine - Metz, 2006

    work page 2006

  29. [29]

    MSOL partitioning problems on graphs of bounded treewidth and clique-width

    Micha \" e l Rao. MSOL partitioning problems on graphs of bounded treewidth and clique-width. Theor. Comput. Sci. , 377(1-3):260--267, 2007. URL: https://doi.org/10.1016/j.tcs.2007.03.043, https://doi.org/10.1016/J.TCS.2007.03.043 doi:10.1016/J.TCS.2007.03.043

    work page doi:10.1016/j.tcs.2007.03.043 2007

  30. [30]

    Monadic second-order model-checking on decomposable matroids

    Yann Strozecki. Monadic second-order model-checking on decomposable matroids. Discret. Appl. Math. , 159(10):1022--1039, 2011. URL: https://doi.org/10.1016/j.dam.2011.02.005, https://doi.org/10.1016/J.DAM.2011.02.005 doi:10.1016/J.DAM.2011.02.005

    work page doi:10.1016/j.dam.2011.02.005 2011