Computing Twin-Width
via Treedepth and Vertex Integrity

In this article, we push beyond the state of the art for computing twin-width in two directions. As our first result, we lift the fixed-parameter approximability of twin-width from the vertex integrity parameterization to treedepth – a well-studied parameter that has fundamental ties to the theory of graph sparsity [35]. In particular, we prove:

Even though the algorithm underlying Main Result 1 (formalized in Theorem 20) provides approximation guarantees only in terms of a superexponential function of the twin-width, we believe it to be a major step forward in our conceptual understanding. Indeed, while all previous parameterizations which supported efficient approximation algorithms for twin-width were based on deletion distance, twin-width itself – as well as major structural parameters such as treewidth and clique-width – are decompositional in nature. Our result thus marks the first time we are able to break the barrier towards decompositional parameters: having bounded treedepth is typically witnessed via a certain type of decomposition (which resembles a bounded-depth tree), but cannot be expressed via a constant number of deletion operations¹¹1We remark that both treedepth and treewidth admit characterizations that rely on vertex deletion operations – however, in both cases the number of such operations is not bounded by the parameter..

A further noteworthy property of Theorem 20 is that the proof does not target the computation of twin-width directly. Instead, it relies on reduction rules which maintain a $2$-approximate bound on the so-called oriented twin-width – a variant of twin-width where contraction sequences only capture information about edges of the original graph in a one-sided way. Oriented twin-width has been proposed and studied already in the pioneering series of works that introduced twin-width [15]; it was known to be functionally equivalent to twin-width [15, Theorem 4.1], and in Section 3 we make this relationship both explicit and constructive. It was suspected that oriented twin-width could be easier to compute, and Theorem 20 yields concrete substance to that claim: the algorithm achieves a $2$-approximation on the oriented twin-width of the input graph, but it is entirely unclear how to obtain any such bound for “vanilla” twin-width.

While our first result relies on allowing for a potentially large approximative error in the twin-width, the second one makes do without this entirely:

Main Result 2 (formalized in Theorem 33) is the first non-trivial parameterized algorithm for computing optimal contraction sequences, and shows that the NP-hardness of the problem can be overcome at least under restrictive parameterizations. Moreover, while its running time guarantees are weak in practice, the underlying algorithm relies on the performance of reduction rules which are easy to implement and guaranteed to preserve the twin-width of the input graph. We remark that both algorithms obtained in this work are deterministic, constructive and rely exclusively on computable functions.

On a high level, the proof of Theorem 20 relies on establishing that every sufficiently large graph of bounded treedepth must have a “redundant” subgraph $H$ – that is, a subgraph which we can find and safely delete from the instance. Recursively applying such a rule will eventually reduce the graph to a problem kernel [18], at which point one may compute a contraction sequence via brute force or any other known algorithm. It is well-known that deleting vertices cannot increase the twin-width of a graph, but for correctness it is also necessary to prove the converse: that by deleting $H$, we have not accidentally reduced the twin-width of $G$. In other words, a redundant subgraph must have the property that it can be reinserted into the graph without increasing the twin-width.

The main obstacle towards approximating twin-width when parameterized by treedepth is that – unlike many problems where the above recursive deletion technique has been successfully applied – reinserting $H$ may require the contraction sequence to have a short subsequence where the twin-width is elevated. In particular, the red degree (see Section 2) can exceed the twin-width bound by a factor of at most $2$, and this can happen both for vertices in $H$ and vertices outside of $H$. For a single reinsertion step this would not be an issue, but the algorithm must be able to perform deletion multiple times, which would then lead to the error gradually snowballing to a factor of $4$, $8$, and so forth. The crucial insight here is that if we instead consider contraction sequences for oriented twin-width, the red degree exceeds the twin-width bound only for vertices inside $H$; in turn, this allows us to isolate the approximation error in clearly delimited and pairwise disjoint parts of the contraction sequence.

For Theorem 33, we build on the very recently introduced Ramsey Pruning technique [19]. The core idea behind that technique is that instead of repeatedly arguing that a single redundant subgraph can be safely reinserted if it is deleted, we use Ramsey-type arguments to argue that every contraction sequence $S$ for $G$ must contain a carefully selected subgraph $Q$ which induces “guiding subsequence” $S^{\prime }$ – a contraction sequence for $Q$ that is highly structured in a precisely defined way. Once defined, the properties of $S^{\prime }$ will allow us to argue that every solution on $Q$ can be lifted to a contraction sequence of width $t$ for an infinite set of supergraphs of $Q$ which also includes $G$. Thus, while we do not directly prove the safeness of performing any single deletion operation, the proof technique guarantees that the existence of a solution (in this case, a contraction sequence of width $t$) is preserved between the first and final graph in the sequence of reduction rules.

The main difficulty that arises when trying to implement the above strategy in the setting of twin-width is that, essentially, the properties of $S^{\prime }$ one can guarantee by invoking the analogous Ramsey-type arguments as in the preceding work [19] are too weak. There, the core idea was to capture pairwise relationships between certain subgraphs of $G$ via color-coded edges in an auxiliary graph, and then employ Ramsey theory to guarantee the existence of a monochromatic subclique. Unfortunately, pairwise relationships do not capture sufficient information to guarantee the ability to expand $S^{\prime }$ into a solution for $G$ (or a supergraph thereof). We solve this by showing that maintaining information about interactions between triplets of certain subgraphs in $G$ does suffice – a complication which necessitates the use of Ramsey hypergraph theory instead of the classical bounds used in [19].

Beyond the computation of twin-width and its associated contraction sequences, a substantial body of work has focused on fixed-parameter algorithms for computing a structural graph parameter $A$ when parameterized by graph parameters different from $A$. The overarching goal of this research direction is to deepen our understanding of the fundamental task of computing the target parameter $A$. Prominent examples include fixed-parameter algorithms for treedepth parameterized by the vertex cover number [32], treewidth parameterized by the feedback vertex number [9], MIM-width parameterized by the feedback edge number and other parameters [24], as well as directed feedback vertex number parameterized by the undirected feedback vertex number [7].

Treedepth and vertex integrity have also served as effective parameterizations for developing algorithms for a variety of hard problems [5, 29, 33, 8, 30, 27, 31]. Moreover, vertex integrity has been studied under several asymptotically equivalent notions in the literature, including the fracture number [23, 28] and starwidth [40].

A treedepth decomposition of a graph $G$ is a pair $(T,f)$, where $T$ is a rooted forest and $f:V(G)\to V(T)$ is a bijective function such that for each $\{u,v\}\in E(G)$, either $f(u)$ is a descendant of $f(v)$ or $f(v)$ is a descendant of $f(u)$. The depth of the treedepth decomposition is the number of vertices in the longest root-to-leaf path in $T$; or ease of presentation, w.l.o.g. we will assume that $f$ is just an identity. The treedepth of a graph $G$, denoted by $\mathrm{𝗍𝖽}(G)$, is the minimum over the depths of all possible treedepth decompositions of $G$. When $G$ is connected, $T$ is a tree. For any vertex $u$ of $T$, we denote by $T_u$ the subtree of $T$ rooted at $u$, and $X_u$ the subgraph $G[V(T_u)]$.

A treedepth decomposition $T$ is nice if, for each node $u\in V(T)$ and each child $w$ of $u$ in $T$, $X_w$ forms a connected component of $X_u\setminus \{u\}$ – in particular, there is a one-to-one correspondence between the subtrees rooted at the children of $u$ in $T$ and the set ${\text{Comp}}_u$ of connected components in $X_u\setminus \{u\}$. It is known that every treedepth decomposition can be transformed into a nice one with a smaller or equal depth via a simple rearrangement argument [38], and that a nice treedepth decomposition of depth $\mathrm{𝗍𝖽}(G)$ can be computed in time $2^{𝒪(\mathrm{𝗍𝖽}{(G)}^2)}\cdot |V(G)|$ [38], see also the recent work [34] on the topic.

For ease of presentation, we say that a subgraph $H$ of $G$ appears in $T$ if there exist a seed vertex $u$ in $T$ such that $H=X_u$. Moreover, we call two subgraphs $X_a$, $X_b$ appearing in $T$ siblings if $a$ and $b$ are siblings in $T$, i.e., have the same parent.

A graph $G$ has vertex integrity $\mathrm{𝗏𝗂}(G)=p$ if $p$ is the smallest integer with the following property: $G$ contains a vertex set $S$ such that for each connected component $H$ of $G-S$, $|V(H)\cup S|\le p$. One may observe that the vertex integrity is upper-bounded by the size of a minimum vertex cover in the graph (i.e., the vertex cover number) plus one. The vertex integrity of an $n$-vertex graph along with a corresponding partition into $S$ and $𝒞=G-S$ can be computed in time $𝒪(p^{p+1}\cdot n)$ [22].

We will employ a known generalization of Ramsey’s classical theorem to edge-colored hypergraphs in order to argue the existence of certain structures in our correctness proof. In particular, the following fact follows directly from the application of Erdős’ and Rado’s improved bound on the Ramsey numbers for multicolored hypergraphs [26, Theorem 1]; see also the recent work on the topic [17] for an overview.

Our notation for twin-width follows the conventions introduced in the recent related works aimed at computing twin-width under more restrictive parameterizations [1, 2]. A trigraph $G$ is a graph whose edge set is partitioned into a set of black and red edges. The set of red edges is denoted $R(G)$, and the set of black edges $E(G)$. The black (resp. red) degree of $u\in V(G)$ is the number of black (resp. red) edges incident to $u$ in $G$. We extend graph-theoretic terminology to trigraphs by ignoring the colors of edges; for example, the degree of $u$ in $G$ is the sum of its black and red degrees.

Given a trigraph $G$, a contraction of two distinct vertices $u,v\in V(G)$ is the operation which produces a new trigraph by (1) removing $u,v$ and adding a new vertex $w$, (2) adding a black edge $wx$ for each $x\in V(G)$ such that $xu$, $xv\in E(G)$, and (3) adding a red edge $wy$ for each $y\in V(G)$ such that $yu\in R(G)$, or $yv\in R(G)$, or $y$ has a black edge to either $v$ or $u$ (but not both). For an integer $p$, a sequence $𝒞=(G=G_1,\mathrm{\dots },G_p)$ is a partial contraction sequence of $G$ if it is a sequence of trigraphs such that for all $i\in [p-1]$, $G_{i+1}$ is obtained from $G_i$ by contracting two vertices; if $p=|V(G)|$ then $G_p$ is the single-vertex graph and we call $𝒞$ a contraction sequence. We call a contiguous subsequence of $𝒞$ a segment. The width of a (partial) contraction sequence $𝒞$ is the maximum red degree over all vertices in all trigraphs in $𝒞$. The twin-width of $G$, denoted $\text{tww}(G)$, is the minimum width of any contraction sequence of $G$, and a contraction sequence of width $\text{tww}(G)$ is called optimal. An example of a contraction sequence is provided in Figure 1.

Let us now fix a contraction sequence $𝒞=(G=G_1,\mathrm{\dots },G_n)$. For each $i\in [n]$, we associate each vertex $u\in V(G_i)$ with a set $\beta (u,i)\subseteq V(G)$, called the bag of $u$, which contains all vertices contracted into $u$. Formally, we define the bags as follows:

• $\mathrm{■}$

  for each $u\in V(G)$, $\beta (u,1):=\{u\}$;

• $\mathrm{■}$

  for $i\in [n-1]$, if $w$ is the new vertex in $G_{i+1}$ obtained by contracting $u$ and $v$, then $\beta (w,i+1):=\beta (u,i)\cup \beta (v,i)$; otherwise, $\beta (w,i+1):=\beta (w,i)$.

Note that if a vertex $u$ appears in multiple trigraphs in $𝒞$, then its bag is the same in all of them, and so we may denote the bag of $u$ simply by $\beta (u)$. Let us fix $i,j\in [n]$, $i\le j$. If $u\in V(G_i)$, $v\in V(G_j)$, and $\beta (u)\subseteq \beta (v)$, then we say that $u$ is a $𝒞$-ancestor of $v$ in $G_i$ and $v$ is the $𝒞$-descendant of $u$ in $G_j$ (clearly, the $𝒞$-descendant is unique). If $H$ is an induced subtrigraph of $G_i$, then $u\in V(G_j)$ is a $𝒞$-descendant of $H$ if it is a $𝒞$-descendant of at least one vertex of $H$. A contraction of $u,v\in V(G_j)$ into $uv\in V(G_{j+1})$ involves $w\in V(G_i)$ if $w$ is a $𝒞$-ancestor of $uv$. Given a contraction sequence $𝒞$ of $G$ and vertex subset $Z\subseteq V(G)$, we let $𝒞[Z]$ denote the restriction of $𝒞$ to $Z$, i.e., the contraction sequence obtained from $𝒞$ by omitting each step that involves vertices outside of $Z$; note that $𝒞[Z]$ is a contraction sequence of $G[Z]$ whose width is upper-bounded by the width of $𝒞$.

The twin-width of a graph with vertex integrity $p$ is upper-bounded by $p$. Indeed, given a vertex set $S$ such that for each connected component $H$ of $G-S$, $|V(H)\cup S|\le p$, we can construct a contraction sequence of width $p$ by processing components in an arbitrary order as follows. We contract the first component $H_1$ into a single vertex $v_1$ (during which the red degree never exceeds $p$). Afterwards, for each unprocessed component $i$, $i\ge 2$, we contract $H_i$ into a single vertex (during which the red degree never exceeds $p$ either) and contract this vertex with $v_{i-1}$ to produce $v_i$.

The oriented variant of twin-width is defined using the same concept of contraction sequences as twin-width, and hence we opt to use primarily shared terminology (as opposed to the homogeneity-based notation of [15]). Intuitively, in oriented twin-width red edges only represent discrepancies between the corresponding bags in a one-directional manner; this will require the individual trigraphs in a contraction sequence to depend not only on the previous trigraph in the sequence but also on the original graph. We formalize below.

An oriented trigraph is a graph whose edge set is partitioned into a set of black undirected edges and red directed edges (arcs). Given an initial graph $G$ and an oriented trigraph $G_{i-1}$ each of whose vertices $z\in V(G_{i-1})$ is associated with a bag $\beta (z,i-1)\subseteq V(G)$, an oriented contraction of two distinct vertices $u,v\in V(G_{i-1})$ is the operation which produces a new oriented trigraph $G_i$ as follows. First, we remove $u,v$ and add a new vertex $w$ where $\beta (w,i)=\beta (u,i-1)\cup \beta (v,i-1)$; for all other vertices, the bags remain the same and so do the edges and arcs not incident to $w$. For each $a\in V(G_i)$ we add a black edge $aw$ if every vertex of $\beta (a,i)$ is adjacent to every vertex of $\beta (w,i)$ in $G$. For each $b\in V(G_i)$ we add a red arc $(w,b)$ if there exist $w_1,w_2\in \beta (w,i)$ and $b_0\in \beta (b,i)$ such that $w_1{b}_0\in E(G)$ and $w_2{b}_0\notin E(G)$. Similarly, for each $c\in V(G_i)$ we add a red arc $(c,w)$ if there exist $c_1,c_2\in \beta (c,i)$ and $w_0\in \beta (w,i)$ such that $c_1{w}_0\in E(G)$ and $c_2{w}_0\notin E(G)$. Notice that an oriented contraction cannot increase the red out-degree of any vertex in $V(G_i)\setminus \{w\}$.

An oriented contraction sequence is then defined analogously as a contraction sequence, but using oriented contractions. The oriented width of an oriented contraction sequence $𝒞$ the maximum red out-degree over all vertices in all trigraphs in $𝒞$. While the oriented twin-width of a graph can be smaller than its twin-width, by comparing the definitions of the two notions of contraction sequences we immediately obtain:

The oriented twin-width of a graph $G$, denoted $\text{otww}(G)$, is the minimum oriented width of any oriented contraction sequence of $G$.