Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO

A (relational) signature $\mathrm{\Sigma }$ is a set of relation symbols, each with an implicitly assigned arity. A structure $G$ over  $\mathrm{\Sigma }$ is called a $\mathrm{\Sigma }$-structure. We denote by ${\mathrm{\Sigma }}^{(k)}:=\mathrm{\Sigma }\cup \{C_1,\mathrm{\dots },C_k\}$ the expansion of $\mathrm{\Sigma }$ by $k$ many new unary predicates, which we can think of as colors. A single element is allowed to have multiple colors, but this will not be important. A ${\mathrm{\Sigma }}^{(k)}$-structure $G^{+}$ is a $k$-coloring of $G$, if $G$ is the $\mathrm{\Sigma }$-structure obtained by forgetting the color predicates in $G^{+}$. For a class of $\mathrm{\Sigma }$-structures $𝒞$, we denote by ${𝒞}^{(k)}$ the class of ${\mathrm{\Sigma }}^{(k)}$-structures consisting of all the $k$-colorings of structures from $𝒞$.

A graph is a $\mathrm{\Gamma }$-structure for the signature $\mathrm{\Gamma }:=\{E\}$ consisting of a single binary relation (called edge relation) that is interpreted symmetrically and irreflexive. For any structure $G$, we use $V(G)$ to refer to its universe: if $G$ is a graph, then $V(G)$ is its vertex set.

We assume familiarity with first-order logic (FO) and monadic second-order logic (MSO). As we model graphs as structures with a binary edge relation, MSO on graphs allows for quantification of vertex sets, but not of edge sets. This is also known as ${\mathrm{MSO}}_1$ in the literature. Counting monadic second-order logic (CMSO) extends MSO for all set variables $X$ and  by the cardinality constraint ${\text{card}}_{r,k}(X)$ that holds true if and only if $|X|\equiv r(modk)$. For a logic $ℒ\in \{\mathrm{FO},\mathrm{MSO},\mathrm{CMSO}\}$ and a signature $\mathrm{\Sigma }$. We use $ℒ[\mathrm{\Sigma }]$ to refer to the set of $ℒ$-formulas over $\mathrm{\Sigma }$. An $ℒ[\mathrm{\Sigma }]$-formula $\phi (\overline{x},\overline{y})$ has the $\mathrm{\ell }$-order-property on a $\mathrm{\Sigma }$-structure $G$, if there exists a sequence ${({\overline{a}}_i)}_{i\in [\mathrm{\ell }]}$ of tuples of elements of $G$, such that for all $i,j\in [\mathrm{\ell }]$ we have $G\vDash \phi ({\overline{a}}_i,{\overline{a}}_j)\iff i⩽j$. The formula $\phi$ has the order-property on a class of $\mathrm{\Sigma }$-structures $𝒞$, if for every $\mathrm{\ell }\in \mathbb{N}$ there is $G\in 𝒞$ such that $\phi$ has the $\mathrm{\ell }$-order-property on $G$. We call a class of $\mathrm{\Sigma }$-structures $ℒ$-stable, if no $ℒ[\mathrm{\Sigma }]$-formula has the order-property on $𝒞$. Moreover, $𝒞$ is monadically $ℒ$-stable if for every $k\in \mathbb{N}$, the class ${𝒞}^{(k)}$ of $k$-colorings from $𝒞$ is $ℒ$-stable.

For a logic $ℒ$, $d\in \mathbb{N}$, and signatures ${\mathrm{\Sigma }}_1$ and ${\mathrm{\Sigma }}_2$, a $d$-dimensional $ℒ$-interpretation $I$ from ${\mathrm{\Sigma }}_1$ to ${\mathrm{\Sigma }}_2$ consists of

• $\mathrm{■}$

  an $ℒ[{\mathrm{\Sigma }}_1]$-formula ${\delta }_I(\overline{x})$ called the domain formula,

• $\mathrm{■}$

  an $ℒ[{\mathrm{\Sigma }}_1]$-formula ${\phi }_{I,R}({\overline{x}}_1,\mathrm{\dots },{\overline{x}}_k)$ for every $k$-ary relation $R$ in ${\mathrm{\Sigma }}_2$,

where $\overline{x}$ and all ${\overline{x}}_i$ are $d$-tuples. Given a ${\mathrm{\Sigma }}_1$-structure $G$, we define the $H:=I(G)$ to be the ${\mathrm{\Sigma }}_2$-structure with the universe $V(H):=\{\overline{a}\in V{(G)}^d:G\vDash {\delta }_I(\overline{a})\}$ and relations $R(H):=\{{\overline{a}}_1\mathrm{\dots }{\overline{a}}_k\in V{(H)}^k:G\vDash {\phi }_{I,R}({\overline{a}}_1,\mathrm{\dots },{\overline{a}}_k)\}$ for every $k$-ary relation $R$ in ${\mathrm{\Sigma }}_2$.

We will use interpretations as a reduction mechanism. The following lemma is crucial for this purpose. It follows by a simple formula rewriting procedure. See, e.g., [20, Thm. 4.3.1].

The above lemma also holds for MSO- and CMSO-interpretations, when restricted to a single dimension. See, e.g., [6, Thm. 7.10]. Higher dimensions are problematic because MSO and CMSO cannot quantify over sets of tuples.

For an interpretation $I$ and a class $𝒞$, we write $I(𝒞)$ for the class $\{I(G):G\in 𝒞\}$. We say $𝒞$ $d$-dimensionally $ℒ$-interprets a class $𝒟$, if there exists a $d$-dimensional $ℒ$-interpretation $I$ such that $𝒟\subseteq I(𝒞)$. We have already seen in the introduction, that the class of all paths is MSO-unstable. Lemma 11 lifts instability to all classes that $1$-dimensionally MSO-interpret it.

Fix a graph $G$ and a partition $𝒫$ of its vertices. For every vertex $v\in V(G)$ we denote by $𝒫(v)$ the unique part $Q\in 𝒫$ satisfying $v\in Q$. Let $F\subseteq {𝒫}^2$ be a symmetric relation. We define $H:=G\oplus (𝒫,F)$ to be the graph with vertex set $V(G)$, and edges defined by the following condition, for distinct $u,v\in V(G)$:

We call $H$ a $𝒫$-flip of $G$. If $𝒫$ has at most $k$ parts, we say that $H$ a $k$-flip of $G$. Flips are reversible: $\left(G\oplus (𝒫,F)\right)\oplus (𝒫,F)=G$; and hereditary: for every $k$-flip $H$ of $G$ and $A\subseteq V(G)$, $H[A]$ is also a $k$-flip of $G[A]$.

It will be convenient to work with flip-partitions that are minimal in the following sense.

Clearly for every two graphs $H$ and $G$ on the same vertex set, there exist irreducible $(H,G)$-flip-witnesses. In particular, as we work with loopless graphs, every flip-relation $F$ can be modified to satisfy the last condition stating that no singleton part is flipped with itself. We now argue that the irreducible flip-witnesses are uniquely determined.

Otherwise, we can merge $Q_1$ and $Q_2$, which contradicts irreducibility. $◀$

For every two graph $H$ and $G$ on the same vertex set, we call $𝒫$ the irreducible $(H,G)$-flip-partition and $F$ the irreducible $(H,G)$-flip-relation, if $𝒫$ and $F$ are the unique irreducible $(H,G)$-flip-witnesses, as justified by Lemma 16.

We will not work with the original definition of bounded shrub-depth, as given in [16], and which we omit from this paper. Instead, we will use an equivalent definition called $\mathrm{\infty }$-flip-flatness [11], which we will define in a moment.

The length of a path is the number of edges it contains, i.e., $P_t$ has length $t-1$. For a graph $G$ and two vertices $u,v\in V(G)$ we define ${\text{dist}}_G(u,v)$ to be the length of a shortest path between $u$ and $v$ in $G$. If no such path exists, then $u$ and $v$ are in different connected components of $G$, and we define ${\text{dist}}_G(u,v):=\mathrm{\infty }$. For $r\in \mathbb{N}$, a graph $G$, and a vertex $v\in V(G)$ let $N_r^G[v]:=\{u\in V(G):{\text{dist}}_G(u,v)⩽r\}$ be the (closed) radius-$r$ neighborhood of $v$. We drop the superscript $G$ if it is clear from the context. For $r\in \mathbb{N}$, we call a set $A\subseteq V(G)$ distance-$r$ independent in $G$ if ${\text{dist}}_G(u,v)>r$ for every two distinct vertices $u,v\in A$. Similarly, $A$ is distance-$\mathrm{\infty }$ independent in $G$ if no two vertices of $A$ are in the same connected component of $G$.

We refer to [24] for an introduction to flatness properties. Crucially, flip-flatness characterizes both monadic FO-stability [10] and bounded shrub-depth [11].

Exhaustive case distinctions are depicted in Figure 7. $◀$

Fix a graph class $𝒞$ as in the statement By the pigeonhole principle and hereditariness, it is sufficient to prove the proposition in two separate cases: either $𝒞$ contains arbitrarily large flipped $H_t$ or it contains arbitrarily large flipped $t{P}_t$.

By Lemma 34, there exists a fixed interpretation $I$ such that every flipped $H_{t+4}$ contains an induced subgraph $H_t^{\star }$ on which $I$ interprets $P_t$. Using this interpretation, we can show that there exists an MSO-sentence ${\phi }_{\mathrm{even}}$ that distinguishing $H_t^{\star }$ and $H_{t+1}^{\star }$ for every $t\in \mathbb{N}$. The sentence ${\phi }_{\mathrm{even}}$ checks whether the interpreted $P_t$ has even length, a property that is easily expressible in MSO. To show that there is no FO-sentence equivalent to ${\phi }_{\mathrm{even}}$, we show that there is a fixed multi-dimensional FO-interpretation $I^{\prime }$ that produces $H_t^{\star }$ from the linear order of size $t$. It is known that for every $q\in \mathbb{N}$ there is $t\in \mathbb{N}$ such that no FO-sentence of quantifier rank $q$ can distinguish ${𝔏}_t$ and ${𝔏}_{t+1}$ [23, Thm. 3.6]. The interpretation $I^{\prime }$ lifts this result to $H_t^{\star }$ and $H_{t+1}^{\star }$, which proves that no FO-sentence is equivalent to the MSO-sentence ${\phi }_{\mathrm{even}}$ on $𝒞$.

If $G$ is a flipped $t{P}_t$ with $t⩾2$, we define ${\mathrm{nibble}}_1(G)$ to be the graph where the first vertex and last vertex of the first path are deleted, and ${\mathrm{nibble}}_2(G)$ to be the graph where the first vertex of the first path and the last vertex of the second path are deleted. Using techniques similar to Lemma 31 we can construct an interpretation $I$ which reverses the flips on $G$. This means $I({\mathrm{nibble}}_1(G))$ is the disjoint union of $t-1$ many $P_t$s and a single $P_{t-2}$; and $I({\mathrm{nibble}}_2(G))$ is the disjoint union of $t-2$ many $P_t$s and two $P_{t-1}$s. Using this interpretation $I$, we can construct an MSO-sentence ${\phi }_{\mathrm{sameParity}}$ which for every graph $G$, that is a flipped $t{P}_t$, distinguishes ${\mathrm{nibble}}_1(G)$ and ${\mathrm{nibble}}_2(G)$. This sentence checks whether all paths of the interpretation have the same parity: they are either all of even or all of odd length. By construction ${\mathrm{nibble}}_1(G)\vDash {\phi }_{\mathrm{sameParity}}$ and ${\mathrm{nibble}}_2(G)\vDash ̸{\phi }_{\mathrm{sameParity}}$. To show that no FO-sentence is equivalent to ${\phi }_{\mathrm{sameParity}}$ on $𝒞$, we construct an FO-interpretation $I^{\prime }$ that produces ${\mathrm{nibble}}_i(G)$ from a coloring of ${\mathrm{nibble}}_i(t{P}_t)$ for both $i\in \{1,2\}$. Here the colors mark the parts of the flip-partition, which means each path is colored the same way. For every FO-sentence $\psi$, there is $t\in \mathbb{N}$ such that $\psi$ cannot distinguish between the colorings of ${\mathrm{nibble}}_1(t{P}_t)$ and ${\mathrm{nibble}}_2(t{P}_t)$: it cannot tell whether two endpoints of the same or of different long paths are missing. Intuitively this is because FO cannot express connectivity. This is easiest to formalize using Hanf locality [19, 13], but the classic Ehrenfeucht-Fraïssé games also work. Again this inexpressibility can be lifted through $I^{\prime }$, which proves that no FO-sentence is equivalent to the MSO-sentence ${\phi }_{\mathrm{sameParity}}$ on $𝒞$. $◀$

While the obstructions we found were sufficient to achieve our goal of characterizing MSO-stability, we initially had a stronger characterization in mind, which we could neither prove nor refute:

As we have seen in Lemma 22, this conjecture holds for every class that is monadically FO-unstable. Even stronger, the $k$-flips of $P_t$s appearing there can be assumed to be periodic. This means, the flip-partition splits the paths in a repeating pattern. This is due to the fact that we have extracted the $k$-flips of $P_t$, by “snaking” along the known obstructions characterizing monadic FO-stability (see Figure 5). The advantage of these periodic flips is that they can be finitely described: for every monadically FO-unstable class $𝒞$ there exists an algorithm that given $t\in \mathbb{N}$, returns a size-$t$ obstruction (a flipped $H_t$ or a $k$-flip of $P_t$) that is contained in $𝒞$. We currently do not know whether classes of unbounded shrub-depth admit such algorithms, as we have little control over how the $t{P}_t$s are flipped. Having such a finite description would help to lift algorithmic hardness results from the class of all paths to every hereditary classes of unbounded shrub-depth. One such result is by Lampis, who shows that there is no fpt MSO model checking algorithm for the class of all paths whose runtime dependence is elementary on the size of the input formula, under the complexity theoretic assumption E $\ne$ NE [22]. Lifting this hardness result to hereditary classes of unbounded shrub-depth would yield another characterization, as it is known that every class of bounded shrub-depth admits elementary fpt MSO model checking [14, 16].

Our Theorem 1 only characterizes shrub-depth on the coarse level, distinguishing between classes of bounded and unbounded shrub-depth. One can ask whether the individual levels of the shrub-depth hierarchy (i.e., classes of shrub-depth $k$ for $k\in \mathbb{N}$) can be characterized similarly. The answer to this is negative, as shrub-depth cannot be meaningfully measured on single graphs, but only on graph classes containing infinitely many arbitrarily large graphs. In particular, every graph class consisting only of a single finite graph has shrub-depth at most 1. A more refined parameter that can also be measured on single graphs is SC-depth. On the coarse level, SC-depth and shrub-depth are equivalent: A graph class has bounded shrub-depth if and only if it has bounded SC-depth [16]. We strongly believe that a more fine-grained analysis of our proofs and the proofs in [28, 11] would yield a functional equivalence between SC-depth and the size of the obstructions we have uncovered in this work. More precisely, for a graph $G$ define $\text{obstruction-depth}(G)$ to be the size $t$ of the largest flipped $H_t$ or flipped $t{P}_t$ contained as an induced subgraph in $G$. We conjecture the following.

Our last question concerns the model theoretic notion of dependence, a second major dividing line that generalizes stability. Similar to FO-stable classes, also FO-dependent classes have recently been shown to admit nice combinatorial characterizations [11]. This raises the question whether also MSO-dependence can be combinatorially characterized. It is natural to conjecture the following.

It is already known that a class has bounded clique-width if and only if it does not CMSO-transduce the class of all graphs [7]. In the full paper we show that this confirms the equivalence $(1)\iff (5)$ of the conjecture. We remark that both of the two equivalence $(1)\iff (2)$ and $(1)\iff (3)$ would imply that every class of unbounded clique-width MSO-transduces the class of all graphs. In turn, this would imply the longstanding Seese’s conjecture stating that the MSO-theory of every graph class of unbounded clique-width is undecidable [30, 6]. This suggests that Conjecture 40 is a tough nut to crack.