CMSO-transducing tree-like graph decompositions \rsuper *

Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté ORCID:https://orcid.org/0000-0003-1838-7744, Eun Jung Kim ORCID:https://orcid.org/0000-0002-6824-0516, Noleen Köhler ORCID:https://orcid.org/0000-0002-1023-6530 · 2024

Read CMSO-transducing tree-like graph decompositions \rsuper * by Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté ORCID:https://orcid.org/0000-0003-1838-7744, Eun Jung Kim ORCID:https://orcid.org/0000-0002-6824-0516, Noleen Köhler ORCID:https://orcid.org/0000-0002-1023-6530 (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-04970.txt.

Introduction

Rutger Campbell and four co-authors give logic based procedures that split graphs into standard parts, in a 2024 paper. Many graph problems ease once a graph is broken into modular, split, or bi join components. A 2006 result produced those splits using a strong logic with an ordering aid.

The new work matches those results with a weaker, counting based logic, which is a notable tightening. Their methods extend beyond graphs to set systems with part like structure and to systems of bipartitions. In each case the procedure outputs the canonical split, the one split that does not depend on choices. The authors frame the gain as doing the same work with leaner logical tools. That matters for the theory of graph algorithms.

Catalog record

CREATORRutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté ORCID:https://orcid.org/0000-0003-1838-7744, Eun Jung Kim ORCID:https://orcid.org/0000-0002-6824-0516, Noleen Köhler ORCID:https://orcid.org/0000-0002-1023-6530
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE111 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-04970

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

CMSO-transducing tree-like graph decompositions \rsuper * Thanks: Rutger Campbell: Supported by the Institute for Basic Science (IBS-R029-C1). Mamadou Moustapha Kanté: Supported by the French National Research Agency (ANR-18-CE40-0025-01 and ANR-20-CE48-0002). Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté ORCID:https://orcid.org/0000-0003-1838-7744, Eun Jung Kim ORCID:https://orcid.org/0000-0002-6824-0516, Noleen Köhler ORCID:https://orcid.org/0000-0002-1023-6530 Abstract . We show that given a graph G G we can C ⁡ MSO \operatorname{C}{\!\!}\operatorname{MSO} -transduce 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 MSO \operatorname{MSO} , a strictly more expressive logic than C ⁡ MSO \operatorname{C}{\!\!}\operatorname{MSO} . Our methods more generally yield C 2 ​ MSO \operatorname{C}_{2}{\!\!}\operatorname{MSO} -transductions of the canonical decomposition of weakly-partitive set systems and weakly-bipartitive systems of bipartitions. \titlecomment \lsuper *An extended abstract of this work was presented at the 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) [ CGK+25 ] . [a] [b] [b] [c,d] [e] 1. Introduction A decomposition of a graph, especially a tree-like decomposition, is a result of recursive separations of a graph and is extremely useful for investigating combinatorial properties such as colourability, and for algorithm design. Such a decomposition also plays a fundamental role when one wants to understand the relationship between logic and a graph class. Different notions of the complexity of a separation motivate different ways to decompose, such as tree-decomposition, branch-decomposition, rank-decomposition and carving-decomposition. Furthermore, some important graph classes can be defined through the tree-like decomposition they admit; cographs with cotrees and distance-hereditary graphs with split decompositions being prominent examples. For a logic \mathsf{L} , an \mathsf{L} -transduction is a non-deterministic map from a class of relational structures to a new class of relational structures using \mathsf{L} -formulas. Transducing a tree-like decomposition is of particular interest. Notably, transducing a decomposition of a graph implies that any property that is definable using a decomposition, is also definable on graphs that admit such a decomposition. Moreover, tree-like decompositions can be often represented by labelled trees, for which the equivalence of recognisability by a tree automaton and definability in CMSO is well known [ Cou90 ] . Hence, it is an interesting question to consider what kind of graph decompositions can be transduced using \mathsf{L} -transductions for some extension \mathsf{L} of \operatorname{MSO} . In a series of papers [ Cou90 , Cou91 , Cou96 , Cou06 ] , Courcelle investigated the relationship between the graph properties that can be defined in an extension of \operatorname{MSO} and the graph properties that can be recognized by a tree automaton. In particular, for graphs of bounded treewidth, Courcelle’s theorem states that any property that is definable in the logic \operatorname{MSO} with modulo counting predicate, denoted \operatorname{C}{\!\!}\operatorname{MSO} , can be recognized by a tree automaton [ Cou90 ] . Combining this result with the linear time algorithm for computing tree-decompositions [ Bod93 ] , yields that \operatorname{C}{\!\!}\operatorname{MSO} model-checking can be done in linear time on graphs of bounded treewidth. The converse statement – whether recognisability by a tree automaton implies definability in \operatorname{C}{\!\!}\operatorname{MSO} on graphs of bounded treewidth – was conjectured by Courcelle in [ Cou90 ] and finally settled by Bojańczyk and Pilipczuk [ BP16 ] . The key step to obtain this result is obtaining a tree-decomposition of a graph via an \operatorname{MSO} -transduction, a strategy which was initially proposed in [ Cou91 ] and is now standard. The obvious next question is whether an analogous result can be proved for graphs of bounded clique-width and for more general combinatorial objects, most notably, matroids representable over a fixed finite field and of bounded branch-width. Due to the above-mentioned strategy, the key challenge is to produce corresponding tree-like decompositions by \operatorname{MSO} -transduction. It is known that clique-width decompositions can be \operatorname{MSO} -transduced for graphs of bounded linear clique-width [ BGP21 ] . However, it is unknown if clique-width decompositions can be \operatorname{MSO} -transduced in general. In fact, this question remained open even for distance-hereditary graphs, which are precisely graphs of rank-width 1 (thus, of constant clique-width). Besides tree-decompositions, the problem of transducing cotrees, and in general hierarchical decompositions such as modular decompositions and split decompositions were considered in the literature [ Cou96 , Cou99 , Cou06 , Cou13 ] . In [ Cou96 ] , Courcelle provides transductions using order-invariant \operatorname{MSO} for cographs and modular decompositions of graphs of bounded modular width. Order-invariant \operatorname{MSO} allows the use of a linear order of the set of vertices and is more expressive than \operatorname{C}{\!\!}\operatorname{MSO} [ GR08 ] . The applicability of these transductions was later generalized using the framework of weakly-partitive set systems 1 1 1 Weakly-partitive set systems are set systems enjoying some nice closure properties, which were then used to show that some set systems allow canonical tree representations, see for instance the thesis by Montgolfier and Rao [ dM03 , Rao06 ] . to obtain order-invariant \operatorname{MSO} -transductions of modular and split decompositions [ Cou06 ] . It was left as an open question whether one can get rid of the order (see for instance [ Cou12 ] where an overview of the result on hierarchical decompositions was given). 1.1. Our results In this paper, we consider decompositions given by separations that do not overlap with any other separations of the same type. We view separations of a given kind as a ‘set system’. A set system consists of a set U , the universe, and a set \mathcal{S} of subsets of U . Two sets overlap if they have non-empty intersection but neither of them is contained in the other. If no two elements in a set system (U,\mathcal{S}) overlap, i.e. the set system is laminar , then the subset relation in (U,\mathcal{S}) can be described by a rooted tree T , called the laminar tree of (U,\mathcal{S}) . For any set system (U,\mathcal{S}) we can look at the subset of strong sets, i.e., sets that do not overlap with any other set, and the laminar tree T they induce. Additionally, we consider systems of bipartitions \mathcal{B} of a universe U . Two bipartitions of U overlap if neither side of one of the bipartition is contained in either side of the other bipartition. In case (U,\mathcal{B}) has no overlapping bipartitions, then (U,\mathcal{B}) can be described by an undirected tree, also called laminar tree , in which bipartitions correspond to edge cuts. We can define the concept of strong bipartitions equivalently and consider the laminar tree induced by the strong bipartitions in (U,\mathcal{B}) . Given a graph G we can consider the set system (V(G),\mathcal{M}) where \mathcal{M} is the set of all modules in G , or the system of bipartition (V(G),\mathcal{S}) where \mathcal{S} contains all splits in G , or the system of bipartitions (V(G),\mathcal{B}) where \mathcal{B} contains all bi-joins in G . We obtain the modular decomposition/cotree/split decomposition/bi-join decomposition by equipping the laminar tree of the suitable set system/system of bipartitions with some additional structure. The additional structure allows us to recover the graph from the respective decomposition. Abstractly, the set systems/systems of bipartitions mentioned are instances of weakly-partitive set systems / weakly-bipartitive systems of bipartitions . Roughly speaking, if a set system (U,\mathcal{S}) is well behaved, i.e. (U,\mathcal{S}) is weakly-partitive

Read the complete text