Twin-Width One

Consider a graph $G$ such that there exists a module $M\subset V(G)$ such that $G-M\in 𝒢$ and $G[M]\in 𝒢$. If $M$ is universal or isolated, $G-M$ is a module of $G$ and, by Lemma 5, $G$ is also a graph of $𝒢$. If $G-M$ admits a partial $1$-contraction sequence $\pi$ ending with edge $\{N(M),\overline{N}(M)\}$, then $\pi$ is also a partial $1$-contraction sequence of $G$, and can be extended to be $1$-contraction sequence of $G$. Indeed, no red edge incident to $M$ appears when applying $\pi$ to $G$ since pairs of contracted vertices are always either in $N(M)$ or $\overline{N}(M)$, we can then apply the $1$-contraction sequence of $M$, and finally contract arbitrarily the resulting 3-vertex trigraph.

Conversely, consider a graph of $𝒢$. It admits a $1$-contraction sequence with a $3$-vertex trigraph $G_3$. $G_3$ has at most one red edge $ab$ (pick $a,b$ arbitrarily in $V(G_3)$ if there is no red edge). We consider $v\in V(G_3)-\{a,b\}$. The set $M$ of vertices of $G$ that were contracted to form $v$ is a module since there are no incident red edges in $G_3$. $G-M\in 𝒢$ and $G[M]\in 𝒢$ since they are induced subgraphs of $G$. Let $A$ and $B$ be the sets of vertices that were contracted to form $a$ and $b$, respectively. Since $v$ has no red neighbour, it must be that $A\subseteq N(M)$ or $A\subseteq \overline{N}(M)$, similarly, $B\subseteq N(M)$ or $B\subseteq \overline{N}(M)$. We conclude that $M$ is universal, isolated or $G-M$ admits a contraction sequence ending with the edge $\{N(M),\overline{N}(M)\}$. $◀$

Given a permutation graph $G=(V,E)$ and $U\subseteq V$, we denote by $\sigma [U]$ and $\tau [U]$ the restrictions of $\sigma$ and $\tau$ (re-numbered by $[|U|]$). They form a realiser of $G[U]$ as a permutation graph. We also use the notation $\sigma \cdot \tau$ to denote the concatenation of two orderings on disjoint domains (all elements of $\sigma$ are before elements of $\tau$, relative orders in $\sigma$ and $\tau$ are preserved).

The following lemma implies Theorem 8.

We proceed by induction on the number of vertices of the graph by leveraging the recursive characterization given in Lemma 10.

The statement is trivial for graphs on at most $3$ vertices. We now consider a graph $G\in 𝒢$ on more than $3$ vertices and its contraction sequence $G_n,\mathrm{\dots },G_3,G_2,G_1$. Let $M$ be the set of vertices of $G$ that were contracted into a vertex of $G_3$ not incident to a red edge in $G_3$, $M$ is a module of $G$. Restricting the sequence $G_n,\mathrm{\dots },G_1$ to $G-M$ and $G[M]$, respectively, yields a $1$-contraction sequence for each of them. By induction hypothesis applied with these sequences, we obtain realisers ${\sigma }_1,{\tau }_1$ and ${\sigma }_2,{\tau }_2$ of $G-M$ and $G[M]$, respectively. The following cases are illustrated in Figure 1. If $M$ is universal (resp. isolated), ${\sigma }_1\cdot {\sigma }_2,{\tau }_2\cdot {\tau }_1$ (resp. ${\sigma }_1\cdot {\sigma }_2,{\tau }_1\cdot {\tau }_2$) is a realiser of $G$. Otherwise, the contraction sequence $G_n-M,\mathrm{\dots },G_3-M$ is such that $V(G_3-M)=\{N(M),\overline{N}(M)\}$. In particular, we know from the induction hypothesis that $B=N(M)$ and $A=\overline{N}(M)$ are intervals of either ${\sigma }_1$ or ${\tau }_1$, as they correspond to the sets of vertices contracted into the last two vertices on the sequence. Without loss of generality, we assume they are intervals of ${\sigma }_1$. We can now produce the realiser ${\sigma }_1[B]\cdot {\sigma }_2\cdot {\sigma }_1[A],{\tau }_2\cdot {\tau }_1$. In all cases, the realiser satisfies the desired properties: it suffices to observe that by construction we do not contract vertices from $G-M$ with vertices from $G[M]$ until the last two contractions, so we must check only the last two contractions which are on trigraphs of order at most $3$ hence the properties are satisfied. $◀$

We now move on to show related properties that will be useful in further understanding permutation diagrams and their relation to contraction sequences.

In the particular case of a prime graph, we deduce the following two corollaries of Lemma 11.

In $G_{n-1}$, let $x^{\prime },z$ be the vertices incident to the red edge (there is a red edge because the graph is prime, see Lemma 7) with $x^{\prime }$ resulting of the contraction of vertices $x$ and $y$ of $G$. $X^{\prime }=\{x,y\}$ is an interval for one ordering $\sigma$ of the realiser. $z$ must be a splitter of $X^{\prime }$ because it is incident to the red edge, this implies that $z$ is between $x$ and $y$ in the ordering $\tau$. $◀$

Unfortunately, there can be linearly many such pairs. On the other hand, there are only $4$ extremal vertices in a prime permutation graph. Hence, the following corollary is useful for obtaining a linear time recognition algorithm.

Due to the graph being prime, the last vertex of $G$ to become incident to the red edge is also a vertex of $G_3$ and is adjacent to exactly one other vertex of $G_3$. The other two vertices of $G_3$ are connected because prime graphs are connected, hence $G_3$ is isomorphic to $P_3$ whose vertices are all extremal. In particular, the last vertex incident to the red edge is extremal. $◀$

We describe how to construct the induced subgraph of $G$ by picking a representative in $G$ for each vertex in $G_i$.

Consider a vertex $v$ of $G_i$, either it has only black incident edges and we may pick any vertex of $G$ that was contracted into $v$, or it has exactly one incident red edge $vw$, in which case we can pick the endpoints of some edge of $G$ that is between the vertices contracted into $v$ and the vertices contracted into $w$.

This construction picks only one vertex of $G$ per vertex of $G_i$ because the red degree is at most one meaning we do not pick more than once. $◀$

This property only holds for $1$-contraction sequences (e.g. contracting non-adjacent vertices of a matching creates a path on $3$ vertices which is not an induced subgraph). It allows to view the contraction sequence as a sequence of vertex deletions. In particular, underlying graphs of the trigraphs of a $1$-contraction sequence are also permutation graphs and one of their permutation diagrams is the induced permutation diagram obtained by seeing $G_i$ as an induced subgraph of $G$. Observe that this diagram preserves the relative order of vertices that are not deleted. This will be important for our inductive reasoning since we can keep the same diagram while decomposing the graph. We denote by $\sigma [G_i]$ the ordering induced by $G_i$ seen as an induced subgraph of $G$.

Suppose we contract $a,b\in V(G_i)$ into vertex $c\in V(G_{i-1})$. Let $C$ be the set of vertices of $G$ contracted into $c$, and $A,B$ those contracted into $a,b$. By Lemma 11, $A$, $B$ and $C$ are all intervals of $(\sigma ,\tau )$. Since $C=A\cup B$, we may assume without loss of generality they are all intervals of $\sigma$. Hence, $a$ and $b$ are consecutive for $\sigma [G_i]$. Similarly, the set of vertices of $G$ contracted into a fixed red edge is an interval of $(\sigma ,\tau )$. Since the sets of vertices of $G$ incident to the red edge are also intervals, this means the endpoints of the red edge in $G_i$ are consecutive.

Now, consider any realiser $({\sigma }^{\prime },{\tau }^{\prime })$ for graph $G$, and let us show the second part of the lemma by induction on the modular decomposition of $G$. The result holds trivially for leaves of the decomposition. Let us then consider an internal node $q$ of the decomposition of $G$ and consider the subgraphs $H_1,\mathrm{\dots },H_k$ of $G$ induced by the children of $q$. Now, since each $H_i$ is a strong module of $G$, they each form a common interval of $({\sigma }^{\prime },{\tau }^{\prime })$ by Observation 3. They also have twin-width $1$, so our induction hypothesis along with Lemma 5 yields that we can contract each child fully by respecting the consecutivity properties on $({\sigma }^{\prime }[H_i],{\tau }^{\prime }[H_i])$, and thus on $({\sigma }^{\prime },{\tau }^{\prime })$. Then, if $q$ is a degenerate node, we can always find a pair of consecutive twins and contract them. Otherwise, $q$ is prime, and as such it admits a unique realiser (up to symmetry), which is given by Lemma 11, for which the contraction sequence satisfies the desired properties by the first part of the lemma. $◀$

Let $(\sigma ,\tau )$ be a realiser of $G$ and $s$ be an extremal vertex for $\sigma$ which is the last vertex incident to the red edge in some $1$-contraction sequence of $G$. Such a vertex exists due to Corollary 13. Let $G^1=G[N(s)]$ and $G^2=G[\overline{N}(s)]$ and observe that since $G$ is prime, $G^1$ and $G^2$ are not empty. As $s$ is extremal for $\sigma$, adjacent to $V(G^1)$ and non-adjacent to $V(G^2)$, $V(G^1)$ and $V(G^2)$ must be disjoint intervals of $\tau$.

Due to the assumption on $s$ being the last vertex incident to a red edge, we cannot contract a vertex of $G^1$ with a vertex of $G^2$, unless $G^1$ and $G^2$ both have been contracted to a single vertex, because they are split by $s$. $\mathrm{⊲}$

Indeed, $M$ cannot be a module of $G$, as $G$ is a prime graph, so it must have a splitter $s^{\prime }$ in $G-V(G^i)$. Also note that $s$ is not a splitter of $M$ by definition of $G^i$. Furthermore, since $s^{\prime }$ is a splitter it must be adjacent to some $a\in M$ and non-adjacent to some $b\in M$. Since $V(G^1)$ and $V(G^2)$ are intervals of $\tau$, we get that or by definition of the permutation diagram. $\mathrm{⊲}$

The following observation will allow to simplify the analysis.

Consider the cut $C=(X\cap N(t),X-N(t))$ in $H[X]$, since $H[X]$ is prime both $H[X]$ and $\overline{H[X]}$ are connected, yielding both an edge and an non-edge across $C$. $◀$

We proceed by contradiction and consider $M,M^{\prime }$ two maximal disjoint non-trivial strong modules of $G^i$, without loss of generality $i=1$. We first show that, in $G$, $M$ and $M^{\prime }$ must have distinct splitters from $V(G^2)$, and then conclude that this contradicts the assumption that $G$ has a $1$-contraction sequence respecting 17.

Using the fact that $V(G^1)$ and $V(G^2)$ are intervals of $\tau$ and the common interval characterisation of strong modules of $G^1$ given by 3, we deduce that a splitter $t$, which necessarily belongs to $V(G^2)$, cannot split both $M$ and $M^{\prime }$. Indeed, we have or , so if $t$ is a splitter of $M$ there exist $a,b\in M$ such that as seen in the previous claim. In particular, $t$ is not a splitter of $M^{\prime }$.

Now because $M$ and $M^{\prime }$ are non-trivial modules of $G^1$, they each have a splitter in $G^2$. Let $t$ and $t^{\prime }$ be such splitters. By maximality, $M$ and $M^{\prime }$ correspond to subtrees rooted at siblings of the same node $n$ in the modular decomposition of $G^1$. Let us first consider the case when $n$ is a prime node. In this case, Lemma 7 guarantees a red edge for $Q(n)$, and the two splitters $t,t^{\prime }$ forbid the existence of a contraction sequence with consecutivity properties as guaranteed by Lemma 11 and Corollary 15.

We may now assume that $n$ is a degenerate node, and exhibit an induced subgraph $H$ of $G$ that does not admit a $1$-contraction sequence respecting our assumptions. This will contradict the existence of such a sequence for the whole $G$, as its restriction to $H$ would also be valid (as in Observation 4). The graph $H$ consists of splitters $t,t^{\prime }$, as well as two pairs of twins $a,b\in M$ and $a^{\prime },b^{\prime }\in M^{\prime }$ distinguished by $t,t^{\prime }$ respectively. Then, vertices $a,b,a^{\prime },b^{\prime }$ induce a cograph whose corresponding cotree is a complete binary tree of depth $2$. In other words, $(a,b)$ and $(a^{\prime },b^{\prime })$ are present if and only if $\{a,b\}$ is adjacent to $\{a^{\prime },b^{\prime }\}$.

We first reduce $M$ and $M^{\prime }$ so as to induce exactly the quotient graph of their corresponding node in the modular decomposition (recall that this is well defined because they are strong) by picking one vertex in each subtree below this node. We may ensure that $t$ and $t^{\prime }$ still split this subset of vertices (e.g. by picking extremal vertices of the interval of $\sigma$ corresponding to $M$ and $M^{\prime }$, recalling 3).

Now we observe that if $M$ (resp. $M^{\prime }$) has a degenerate root node, it is of the opposite type of the node $n$, and any pair of vertices of $M$ (resp. $M^{\prime }$) that is split by $t$ (resp. $t^{\prime }$) can be taken for our subgraph $H$. Otherwise, $M$ (resp. $M^{\prime }$) has a prime root node, and we apply Observation 19 to obtain a pair of vertices that is split and has the required adjacency relation.

Let us now show that $H$ does not admit a $1$-contraction sequence satisfying our assumptions. Indeed, $t$ and $t^{\prime }$ may only be contracted together, because they are the only vertices in $V(G^2)$ of our subgraph (Claim 17), but they are split by at least two vertices in $V(G^1)$. Now, any order of contractions on $a,b,a^{\prime },b^{\prime }$ will create two red edges. More precisely, contracting a vertex from each nontrivial module creates two red edges, unless one module was already reduced to a single vertex, in which case it has a red edge to its splitter from $V(G^2)$. This will inevitably contradict Lemma 7. $\mathrm{⊲}$

Let $p$ be a prime node of the modular decomposition of $G^i$ and $M$ the module corresponding to the subtree rooted at $p$. Without loss of generality assume $i=1$. We first make the observation that, since there cannot be two disjoint nontrivial strong modules in $G^1$ by 20, and since prime graphs have at least $4$ vertices, there are vertices introduced by node $p$.

We first consider the case when a red edge incident to a vertex of $G^2$ is created before we fully contract $M$. This red edge has to remain incident to a vertex of $G^2$ due to Claim 17. Contracting a vertex introduced in prime node $p$ will create another red edge with both endpoints in $G^1$, which is thus different and contradicts Lemma 7.

We now deal with the case where no red edge incident to a vertex of $G^2$ appears before we fully contract $M$. Assume the first red edge does not have both endpoints in $M$. Observe that the first contraction cannot be between vertices that are both not in $M$ but have a different adjacency to it because $M$ is a module on at least $4$ vertices, and this would create a red edge to all of them. Observe also that if the first contraction had involved a vertex of $M$, there would also be a red edge with both endpoints in $M$. Indeed, on the one hand, if both contracted vertices were in $M$, red edges with both endpoints in $G^i$ would have both endpoints in $M$ because it is a module. On the other hand, $M$ is also a strong module with a prime node at its root, so all of its vertices have a mixed adjacency to the rest of $M$, contrary to vertices outside $M$. We conclude that the first contraction is between two vertices outside of $M$, so the corresponding red edge has both endpoints outside of $M$. This has the following implications: both contracted vertices have an homogeneous adjacency to $M$, but they also have a unique splitter in $G^1$, this implies we cannot contract the red edge before contracting the subgraph corresponding to $p$. Indeed, the two vertices incident to the red edge must have opposite adjacency relations with respect to $M$. Since contracting $M$ will force the creation of a second red edge, this contradicts Lemma 7.

$M$ is a non-trivial strong module of $G^1$ so it has at least one splitter in $G^2$. From Lemma 7 and Claim 17, it follows that a red edge incident to this splitter cannot appear before $M$ is contracted to a single vertex. Finally, only one red edge may appear when $M$ is contracted to a single vertex meaning the splitter must be unique. $\mathrm{⊲}$

In particular, this shows that only one of $G^1$ and $G^2$ can have a prime node in their modular decomposition. We can moreover deduce that if there is a prime node in $G^i$, it must be unique. Indeed, a red edge has to appear in some $M$ corresponding to the subtree of the prime node that is deepest in the modular decomposition of $G^i$. At any step of the sequence, $M$ contains a red edge, until it is a single vertex with a red edge towards its splitter. Then, vertices introduced in any higher prime node cannot be contracted on such red edges without producing an additional red edge, which contradicts Lemma 7.

We are now ready to define $M$. Consider the first red edge appearing between $X_1\subseteq V(G^1)$ and $X_2\subseteq V(G^2)$ in a $1$-contraction sequence as considered, and assume without loss of generality that it stems from a contraction in $G^1$. Then, $X_2$ can only consist in a single vertex $s^{\prime }$ due to Claim 17, Lemma 7, and the fact that this is the first red edge with an endpoint in both $G^1$ and $G^2$. Then, $X_1$ is included in a module of $G^1$ which admits as unique splitter $s^{\prime }$. In the case when there is no prime node, $X_1$ induces a cograph, so we may then take $M$ to be any pair of consecutive twins $a,b\in X_1$, which are also consecutive twins in $G^1$ by Corollary 15, distinguished by $s^{\prime }$ (because $G$ is prime and $s^{\prime }$ is the only splitter of $X_1$).

Otherwise, we can take $M$ and $s^{\prime }$ as guaranteed by 21 on $G^1$ and $G^2$. The restriction of our contraction sequence to $G[M\cup s^{\prime }]$ yields a $1$-contraction sequence in which $s^{\prime }$ becomes incident to a red edge last, as desired.

Having defined $M$, we are ready to show the following.

We can extend the contraction sequence that contracts $M$ first into a sequence contracting the smallest interval $I$ of $\sigma [V(G^1)]$ containing $X_1$ because $X_1$ is not split by any splitter from $G^2$ other than $s^{\prime }$, and it does not have disjoint non trivial strong modules. After contraction of $M$ to a single vertex, the remaining vertices of $I$ induce a cograph that is not split by any vertex of $G^2$ other than $s^{\prime }$. We can then proceed with the rest of the contraction of $G$ simply by contracting remaining vertices according to our initial contraction sequence. $\mathrm{⊲}$

At this point, in both cases, we know $M$ forms a common interval for $(\sigma [V(G^1)],\tau [V(G^1)])$, and that there is some $1$-sequence for $G$ that first contracts $M$ and in which $s$ is the last vertex to be incident to a red edge. We deduce that $M\cup \{s^{\prime }\}$ satisfies the setting of Corollary 15, and any further contractions must be consecutive to $M$ due to Corollary 15, ensuring the existence of $\pi$. $◀$

The crucial observation now is that $\pi$ can easily be computed greedily using the realiser.

This is essentially an implementation of the result of Lemma 16, we reuse similar notations and provide an illustration in Figure 2. The algorithm works as follows.

We initialise indices at the endpoints of the intervals $A$ and $B$ of $\tau$ that are split by $s$, and at the endpoints of the interval $C=V(G)-\{s\}$ of $\sigma$. We add $s$ to the global list $\mathrm{\Pi }$ and mark it as a splitter.

While there is one endpoint $v$ of $C$ that is also an endpoint of $A$ or an endpoint of $B$, we add $v$ to the global list $\mathrm{\Pi }$ and update indices describing $A,B,$ and $C$ in accordance to the removal of $v$. We call such a vertex $v$ doubly extremal.

If the intervals have become empty, return $\mathrm{\Pi }$, otherwise, if either $A$ or $B$ contains a single vertex, we set $s^{\prime }$ to be this vertex and $M$ to be the other interval, and apply the algorithm recursively to $G[M\cup \{s^{\prime }\}]$ with $s^{\prime }$ as the last vertex incident to a red edge. Finally, if both $A$ and $B$ contain more than one vertex, we reject.

We can use marked vertices to deduce a contraction sequence: we iterate through $\mathrm{\Pi }$, starting from the last vertices added. When reaching a marked vertex, we contract the red edge. Otherwise, we contract the current vertex to the vertex of the red edge with the same adjacency to the next marked vertex.

If the algorithm does not reject, let us show by induction on the recursive calls that the list $\mathrm{\Pi }$, along with its marked vertices, describes a valid order of contractions for $G$. First, we clarify the starting red edge that we consider in the part of the contraction sequence built at this step of the recursion. In the case when we emptied $A$ and $B$ (so $M$ and $s^{\prime }$ are not defined), take the last vertex in $A$ and the last vertex in $B$ as a starting red edge. We move to the case where $M$ and $s^{\prime }$ are defined. Here, by induction hypothesis, the algorithm finds a $1$-contraction sequence with $s^{\prime }$ as the last vertex incident to a red edge for $G[M\cup \{s^{\prime }\}]$. This contraction sequence for $G[M\cup \{s^{\prime }\}]$ gives a partial $1$-contraction sequence for $G$ (see Observation 4) yielding a red edge between $M$ and $s^{\prime }$, with all other vertices of $G$ not contracted yet.

We now check that each vertex added to $\mathrm{\Pi }$ at this step can be contracted in the order described by $\mathrm{\Pi }$. This is the case because the vertex does not split the vertices of $A$ contracted before it, nor the vertices of $B$ contracted before it. By contracting it to the vertex of the red edge with the same adjacency to $s$, we create no additional red edge. In particular, $s$ is still not incident to a red edge. Once we contracted all vertices of $A$ and $B$, the red edge can be safely contracted. Indeed, $s$ is the unique splitter of $A\cup B$.

If the algorithm rejects, it contradicts the existence of $\pi$ guaranteed by Lemma 16. Indeed, if for all $i$, the $M\cup \{s^{\prime }\}\cup \pi ([i])$ are intervals as claimed, it must be that for each $i$, $\pi (i)$ is extremal on $\sigma [M\cup \{s^{\prime }\}\cup \pi ([i])]$ and on $\tau [(M\cup \{s^{\prime }\}\cup \pi ([i]))\cap V(G^j)]$ for some $j\in \{1,2\}$. In particular, all vertices that are not in $M\cup \{s^{\prime }\}$ will become doubly extremal if $\pi$ exists. Note that this is independent of the order in which they are contracted. Indeed, a vertex remains (doubly) extremal while we delete other vertices.

We conclude that $G$ has twin-width more than $1$. $◀$

We first compute a modular decomposition of $G$ and realisers for the quotient graphs of prime nodes [24]¹¹1In fact, it would be more reasonable to compute a permutation diagram and deduce a modular decomposition via common intervals for a practical implementation., or conclude that $G$ is not a permutation graph and therefore not a graph of twin-width $1$. It is well-known that the total size of the quotient graphs of prime nodes is linear in the size of the original graph.

We then check all prime nodes with corresponding quotient graph $H$ as follows:

Guess an extremal vertex $s$ (out of at most $4$) that can be the last vertex incident to the red edge in a $1$-contraction sequence of $H$, and then apply the recursive algorithm of Lemma 23.

If all prime nodes have twin-width $1$, we obtained a contraction sequence for all of them and they can be combined to form a contraction sequence of $G$ using Corollary 6.

All of the above procedures can be implemented to run in linear time. $◀$