First-Order Logic and Twin-Width for Some Geometric Graphs

Let $𝒟$ be the graph class we are interested in, e.g. the class of all circular-arc graphs. Our goal is the following: for any hereditary²²2The hereditary assumption is necessary to avoid classes in which model checking is easy for trivial reasons, such as graphs of the form: a complex graph on $n$ vertices, plus $2^n$ isolated vertices as padding. subclass $𝒞\subseteq 𝒟$, there is an FPT model checking algorithm in $𝒞$ if and only if $𝒞$ has bounded twin-width. Inspired by [1, 15], we obtain such an equivalence by proving a dichotomy of the following form, for any subclass $𝒞\subseteq 𝒟$:

• $\mathrm{■}$

  Either we can compute in polynomial time a contraction sequence for any $G\in 𝒞$, witnessing that $G$ has bounded twin-width. Then [4] gives FPT model checking in $𝒞$.

• $\mathrm{■}$

  Or $𝒞$ is monadically independent, which informally means that graphs in $𝒞$ can be used to encode arbitrary graphs through FO logic (this is formalised by FO transductions, see Section 2.4 for the definition). In that case, and if $𝒞$ additionally is hereditary, then FO model checking on the class of all graphs reduces to FO model checking on $𝒞$ [9], proving that the latter is hard for the parametrised complexity class $\mathrm{𝖠𝖶}[\ast ]$ [8].

Let us point out that if $𝒞$ has bounded twin-width, then it is monadically dependent (the opposite of monadically independent). Thus a subclass $𝒞\subseteq 𝒟$ has bounded twin-width if and only if it is monadically dependent; this is the precise definition of delineation in [1]. The above dichotomy is a slight strengthening of delineation, additionally requiring to be able to efficiently find contraction sequences. When $𝒞$ is hereditary, and assuming $\mathrm{𝖥𝖯𝖳}\ne \mathrm{𝖠𝖶}[\ast ]$, this strengthening gives the equivalence of $𝒞$ having bounded twin-width, $𝒞$ being monadically dependent, and $𝒞$ admitting an FPT model checking algorithm. Let us point out that it is a major conjecture in finite model theory that the last two points are always equivalent:

Our results confirm special cases of this, where twin-width explains the equivalence.

Coming back to the proof overview, let us explain how the previously stated dichotomy is achieved. The starting point is the characterisation of twin-width through obstructions in matrices [4]: given any 0–1 matrix $M$, one can efficiently find either a contraction sequence for $M$ (witnessing small twin-width), or a grid. Given the geometric representation of the graph $G$, we construct some auxiliary matrix $M_G$. For instance, for circular arc graphs, we identify the circle with $\{1,\mathrm{\dots },n\}$ modulo $n$, and the matrix $M$ has a 1 at position $(i,j)$ whenever there is an arc clockwise from $i$ to $j$. We then prove two facts:

• $\mathrm{■}$

  First, $G$ can be reconstructed from $M_G$ by a sequence of operations that preserve twin-width. Thus if $M_G$ has bounded twin-width, then so does $G$. This is efficient: a contraction sequence for $G$ can quickly be computed from one for $M_G$.

• $\mathrm{■}$

  Second, if $M_G$ contains a sufficiently large grid, then $G$ contains a complex structure called a transversal pair. It is known that if graphs in $𝒞$ contain arbitrarily large transversal pairs, then $𝒞$ is monadically independent [1].

Thus either one can find contraction sequences for the auxiliary matrices $\{M_G:G\in 𝒞\}$, and thus also for $𝒞$, or these matrices have arbitrarily large grids, hence $𝒞$ contains arbitrarily large transversal pairs and is monadically independent. The case of APUS graphs requires one additional step: we construct local auxiliary matrices, corresponding to 1-by-1 squares in the segment representation. If any such matrix has a grid, then we find a transversal pair; if all local matrices have bounded twin-width, then so does the full graph.

For a graph $G=(V,E)$, we write $V(G)=V$ and $E(G)=E$ for its vertex and edge sets. The set of neighbours of $v\in V(G)$ is $N(v)$. Vertices $x,y$ are twins if $N(u)\setminus \{v\}=N(v)\setminus \{u\}$ ($xy$ may or not be an edge). For $X\subseteq V$, $G[X]$ is the subgraph induced by $X$. When is a linear ordering of $V(G)$, we denote by the adjacency matrix with rows and columns ordered by . Similarly, if and are orderings of $V$ and $E$, then is the incidence matrix with rows and columns ordered by and .

More generally, a binary relational structure (or simply binary structure) $(V,E_1,\mathrm{\dots },E_{\mathrm{\ell }})$ consists of a vertex set $V$, and relations $E_i\subseteq V^2$. It can be viewed as a directed graph with $\mathrm{\ell }$ kinds of edges, where there may be several edges of different kinds between two vertices (but not multiple edges of the same kind). Given a linear ordering of $V$, one defines the adjacency matrix of each relation $E_i$, denoted by . An ordered binary structure is a binary structure in which one of the relations is a linear ordering of the vertex set, normally denoted by . The structure is thus of the form . A special case is ordered graphs , where $(V,E)$ is a graph and a linear ordering of $V$.

The following notion of grids comes from [14]. Given a point $p\in {ℝ}^2$, we write ${\pi }_x(p),{\pi }_y(p)$ for its $x$- and $y$-coordinates. A $t$-grid in the plane is a family of points ${(p_{i,j})}_{i,j\in [t]}$ satisfying the following for any $i,i^{\prime },j,j^{\prime }\in [t]$:

Observe that there are intervals and of $ℝ$ such that $p_{i,j}\in X_i\times Y_j$: take $X_i$ to be the smallest interval containing ${\pi }_x(p_{i,j})$ for all $i$, and similarly with $Y_j$.

This extends to 0–1 matrices, interpreting a one at position $(i,j)$ in the matrix $M$ as a point with coordinates $(i,j)$. We say that $M$ contains a $t$-grid if the point set defined by the ones in $M$ contains a $t$-grid in the previous sense. Then there are partitions into intervals and of the rows and columns as above. The ordering of rows and columns is crucial, which is why we make it explicit in .

The Ramsey property for grids easily follows from the Ramsey theorem on bicliques:

When the $x$- and $y$-coordinates of the grid are indexed by the same set (e.g. in an adjacency matrix), they can be assumed to come from disjoint intervals at a slight cost:

The following technical lemma relates grids in incidence and adjacency matrices.

Twin-width [4] is defined by contraction sequences: a contraction sequence of width $k$ is a witness that the twin-width $\mathrm{𝗍𝗐𝗐}(G)$ is at most $k$. We omit this definition, as we do not directly manipulate contraction sequences, instead relying on higher level results. It suffices to know that twin-width $\mathrm{𝗍𝗐𝗐}(G)$ is well-defined when $G$ is a graph or a binary structure.

We will use the following observation, which is the origin of the name “twin-width”.

The fundamental characterisation of twin-width is that it corresponds to ordered graphs whose adjacency matrix excludes some high-rank grid-like structures [3, Theorem 7]. This characterisation is furthermore efficient. It is simple to check that these high-rank grids contain our notion of grid, hence this implies the following.

Ordered graphs of high twin-width have a Ramsey-like property:

A relational signature is a set $\mathrm{\Sigma }$ of relation symbols $R\in \mathrm{\Sigma }$, each with an arity $r\in \mathbb{N}$. In this work, we will only use unary and binary symbols, i.e. with arity 1 or 2. A $\mathrm{\Sigma }$-structure $S$ consists of a vertex set $V(S)$, and an interpretation of each symbol $R\in \mathrm{\Sigma }$ as a relation $R(S)\subseteq {(V(S))}^r$ of appropriate arity. Thus a unary symbol $U$ is interpreted as a vertex subset, and a binary symbol as a set of directed edges with loops. For instance, graphs are $\{E\}$-structures, and ordered graphs are -structures (with binary symbols).

FO formulas $\varphi$ over a signature $\mathrm{\Sigma }$ consist of quantifiers over vertices $\forall x,\varphi$, $\exists x,\varphi$, boolean operators $\vee ,\wedge ,\neg$, and predicates $R(x_1,\mathrm{\dots },x_r)$ testing whether $(x_1,\mathrm{\dots },x_r)$ is a tuple in the interpretation of $R$, as well as the equality predicate $x=y$. For example,

is a formula over the signature $\{E\}$ (for graphs) expressing that $x,y$ are at distance at most two. When the formula $\varphi$ has free variables, they are written as arguments of $\varphi$ as above. A formula without free variables is called a sentence. If $\varphi (x_1,\mathrm{\dots },x_r)$ is a formula over $\mathrm{\Sigma }$, $S$ is a $\mathrm{\Sigma }$-structure, and $v_1,\mathrm{\dots },v_r\in V(S)$ are vertices, then $S\vDash \varphi (v_1,\mathrm{\dots },v_r)$ denotes that $\varphi$ is satisfied by $S$, with the variables $x_1,\mathrm{\dots },x_r$ interpreted as $v_1,\mathrm{\dots },v_r$ respectively.

The FPT model checking algorithm for twin-width shows the following.

Given two signatures $\mathrm{\Sigma },\mathrm{\Gamma }$, an FO interpretation $\mathrm{\Phi }$ from $\mathrm{\Sigma }$ to $\mathrm{\Gamma }$ is a map, defined in FO logic, from $\mathrm{\Sigma }$-structures to $\mathrm{\Gamma }$-structures. Precisely, $\mathrm{\Phi }$ is described by giving

1. 1.

   for each symbol $R\in \mathrm{\Gamma }$ of arity $r$, an FO formula ${\varphi }_R(x_1,\mathrm{\dots },x_r)$ over $\mathrm{\Sigma }$, and

2. 2.

   one last FO formula ${\varphi }_V(x)$ again over $\mathrm{\Sigma }$.

Given a $\mathrm{\Sigma }$-structure $S$, its image $\mathrm{\Phi }(S)$ is the relational structure where the vertex set is restricted to vertices satisfying ${\varphi }_V$, i.e.

and for each symbol $R\in \mathrm{\Gamma }$, the relation set $R(\mathrm{\Phi }(S))$ is described by ${\varphi }_R$, i.e.

Transductions are a non-deterministic generalisation of interpretations, i.e., a $\mathrm{\Sigma }$-to-$\mathrm{\Gamma }$ transduction outputs a set of $\mathrm{\Gamma }$-structures, rather than a single one. Let $\mathrm{\Sigma }$ be a signature, and $U_1,\mathrm{\dots },U_k$ be $k$ unary symbols, disjoint from $\mathrm{\Sigma }$. The $k$-colouring is the one-to-many operation which maps a $\mathrm{\Sigma }$-structure $S$ to all possible extensions of $S$ as $(\mathrm{\Sigma }\uplus \{U_1,\mathrm{\dots },U_k\})$-structures $S^{+}$, meaning that $V(S)=V(S^{+})$ and $R(S)=R(S^{+})$ for any $R\in \mathrm{\Sigma }$, while the $U_i(S^{+})$ are chosen as arbitrary subsets of $V(S^{+})$. An FO transduction is the composition of a $k$-colouring (for fixed $k$), followed by an FO interpretation.

It is folklore that interpretations and transductions can be composed.

Transductions preserve bounded twin-width, and this can be made efficient.

A graph class $𝒞$ is called monadically independent if it FO transduces the class of all graphs, i.e. if there exists a transduction $\mathrm{\Phi }$ such that $\mathrm{\Phi }(𝒞)$ contains all graphs. If there is no such transduction, then $𝒞$ is called monadically dependent. Theorem 13 implies that bounded twin-width classes are monadically dependent.

To prove that a class $𝒞$ is monadically independent, we will use the next construction, proposed in [1]. Our definition differs slightly, but the idea and purpose are the same.

Given a set family $ℱ$, the intersection graph $G_{ℱ}$ is defined with $ℱ$ as its vertex set, and an edge between $A,B\in ℱ$ if and only if $A\cap B\ne \mathrm{\varnothing }$. The family $ℱ$ is a representation of $G_{ℱ}$.

In an APUS family $ℱ$, for $s,t\in \mathbb{Z}$, denote by ${\mathscr{H}}_{s,t}$ the subset of segments $\mathrm{𝖧𝗈𝗋}(x,y)$ where $x\in [s,s+1)$ and $y\in [t,t+1)$, and define ${𝒱}_{s,t}$ similarly for vertical segments. Clearly the sets ${\mathscr{H}}_{s,t},{𝒱}_{s,t}$ for $s,t\in \mathbb{Z}$ partition $ℱ$. Also, observe that segments in ${\mathscr{H}}_{s,t}$ and ${𝒱}_{s^{\prime },t^{\prime }}$ can intersect only if $s^{\prime }\in \{s,s+1\}$ and $t^{\prime }\in \{t-1,t\}$. Let ${ℱ}_{s,t,\mathrm{⌝}}$ denote the set ${\mathscr{H}}_{s,t}\cup {𝒱}_{s,t}$, and $E_{s,t,\mathrm{⌝}}$ the edges of $G_{ℱ}$ contained in ${ℱ}_{s,t,\mathrm{⌝}}$ that come from segments intersecting in the unit square $[s,s+1)\times [t,t+1)$, for segments coming from the right and top sides of this square (hence $\mathrm{⌝}$ in the notation). Similarly, define ${ℱ}_{s,t,\mathrm{⌜}}={\mathscr{H}}_{s-1,t}\cup {𝒱}_{s,t}$, ${ℱ}_{s,t,\mathrm{⌟}}={\mathscr{H}}_{s,t}\cup {𝒱}_{s,t-1}$, and ${ℱ}_{s,t,\mathrm{⌞}}={\mathscr{H}}_{s-1,t}\cup {𝒱}_{s,t-1}$, as well as $E_{s,t,\mathrm{⌜}},E_{s,t,\mathrm{⌟}},E_{s,t,\mathrm{⌞}}$ the corresponding edge sets. The sets $E_{s,t,d}$ for $s,t\in \mathbb{Z}$ and $d\in \{\mathrm{⌝},\mathrm{⌜},\mathrm{⌟},\mathrm{⌞}\}$ partition the edge set of $G_{ℱ}$. We work on each $E_{s,t,d}$ independently with the techniques of Section 3, and show that when all have bounded twin-width, then so does $G_{ℱ}$. Let us start with the latter.

In general, edge partitions do not preserve bounded twin-width, but they do for ordered graphs (Theorem 9). To use this result, we define an ordering of segments.

A natural attempt is to take the lexicographic ordering of segments, i.e. if and only if , or $x=x^{\prime }$ and , and similarly for vertical segments. However this works poorly with twin-width: consider a family of segments $ℱ=\{h_1,\mathrm{\dots },h_n,v_1,\mathrm{\dots },v_n\}$ such that $h_i,v_i$ intersect close to $(0,2i)$. In particular, $h_i,v_j$ do not intersect for $i\ne j$. By slightly tweaking their $x$-coordinates, any permutation of $v_1,\mathrm{\dots },v_n$ can be realised as the lexicographic ordering . Thus even for these very simple segment families, the ordered intersection graph can be an arbitrary ordered matching, which are known to have unbounded twin-width (see e.g. [3]).

The solution is to have two layers of lexicographic ordering, at local and global scales. That is, we first order the sets ${\mathscr{H}}_{s,t}$ lexicographically by $(s,t)$, and then inside each ${\mathscr{H}}_{s,t}$ order the segments $\mathrm{𝖧𝗈𝗋}(x,y)$ lexicographically as in . The same ordering applies to vertical segments. Finally, all horizontal segments are placed before all vertical ones. Crucially, in , and unlike , each set ${\mathscr{H}}_{s,t}$ or ${𝒱}_{s,t}$ is an interval.

For an APUS family $ℱ$ with intersection graph $G$, denote by the same intersection graph ordered by . Further, for $s,t\in \mathbb{Z}$ and $d\in \{\mathrm{⌝},\mathrm{⌜},\mathrm{⌟},\mathrm{⌞}\}$, let be the restriction to ${ℱ}_{s,t,d}$.

Let us now focus on each $G_{s,t,d}^{\mathrm{𝗌𝖾𝗀}}$, to find either bounded twin-width or a transversal pair.

Here, it must be mentioned that the graph $G_{s,t,d}^{\mathrm{𝗌𝖾𝗀}}$ is the complement of a circular arc graph, see Figure 4. It is thus not surprising that the techniques of Section 3 can be adapted. The results however cannot be applied as a blackbox: to construct transversal pairs when the matrix $M_{{ℱ}_{s,t,d}}$ has a large grid, we may also need segments outside ${ℱ}_{s,t,d}$.

We first show that if $M_{{ℱ}_{s,t,d}}$ has no $k$-grid, its intersection graph has bounded twin-width. By symmetry, it is enough to prove the result for ${ℱ}_{0,0,\mathrm{⌝}}$. The only difference with Lemma 18 is that we now care about the ordered graph, with ordering .

We now show that when $M_{{ℱ}_{s,t,d}}$ does contain a grid, then $G_{ℱ}$ contains a transversal pair. As in Section 3, this requires some minimality hypothesis. We assume discrete coordinates as in Section 2.5, i.e. in an APUS family $ℱ$, the coordinates of segments are non-negative multiples of some $\eta (ℱ)>0$. Subject to this condition, call $ℱ$ minimized if its segments cannot be pushed towards the bottom-left while preserving the intersection graph. Formally, for a fixed $\eta =\eta (ℱ)$, we say that $ℱ$ is minimized if there is no other family ${ℱ}^{\prime }$ with the same $\eta =\eta ({ℱ}^{\prime })$ such that there is a bijection $\varphi :ℱ\to {ℱ}^{\prime }$ that preserves the vertical/horizontal orientation and induces an isomorphism of the intersection graphs, and such that the endpoints of $\varphi (s)$ are coordinate-wise no larger than that of $s$.