Twin-width

Twin-width is defined for finite simple undirected graphs. These have a finite set of vertices, and a set of edges that are unordered pairs of vertices. The open neighborhood of any vertex is the set of other vertices that it is paired with in edges of the graph; the closed neighborhood is formed from the open neighborhood by including the vertex itself. Two vertices are true twins when they have the same closed neighborhood, and false twins when they have the same open neighborhood; more generally, both true twins and false twins can be called twins, without qualification.[1]

The cographs have many equivalent definitions,[2] but one of them is that these are the graphs that can be reduced to a single vertex by a process of repeatedly finding any two twin vertices and merging them into a single vertex. For a cograph, this reduction process will always succeed, no matter which choice of twins to merge is made at each step. For a graph that is not a cograph, it will always get stuck in a subgraph with more than two vertices that has no twins.[1]

The definition of twin-width mimics this reduction process. A contraction sequence, in this context, is a sequence of steps, beginning with the given graph, in which each step replaces a pair of vertices by a single vertex. This produces a sequence of graphs, with edges colored red and black; in the given graph, all edges are assumed to be black. When two vertices are replaced by a single vertex, the neighborhood of the new vertex is the union of the neighborhoods of the replaced vertices. In this new neighborhood, an edge that comes from black edges in the neighborhoods of both vertices remains black; all other edges are colored red.[1]

A contraction sequence is called a ${\displaystyle d}$-sequence if, throughout the sequence, every vertex touches at most ${\displaystyle d}$ red edges. The twin-width of a graph is the smallest value of ${\displaystyle d}$ for which it has a ${\displaystyle d}$-sequence.[1]

A dense graph may still have bounded twin-width; for instance, the cographs include all complete graphs. A variation of twin-width, sparse twin-width, applies to families of graphs rather than to individual graphs. For a family of graphs that is closed under taking induced subgraphs and has bounded twin-width, the following properties are equivalent:[3]

• The graphs in the family are sparse, meaning that they have a number of edges bounded by a linear function of their number of vertices.
• The family does not include all complete bipartite graphs.
• The family of all subgraphs of graphs in the given family has bounded twin-width.
• The family has bounded expansion, meaning that all its shallow minors are sparse.

Such a family is said to have bounded sparse twin-width.[3]

The concept of twin-width can be generalized from graphs to various totally ordered structures (including graphs equipped with a total ordering on their vertices), and is in many ways simpler for ordered structures than for unordered graphs.[4] It is also possible to formulate equivalent definitions for other notions of graph width using contraction sequences with different requirements than having bounded degree.[5]

Cographs have twin-width zero. In the reduction process for cographs, there will be no red edges: when two vertices are merged, their neighborhoods are equal, so there are no edges coming from only one of the two neighborhoods to be colored red. In any other graph, any contraction sequence will produce some red edges, and the twin-width will be greater than zero.[1]

The path graphs with at most three vertices are cographs, but every larger path graph has twin-width one. For a contraction sequence that repeatedly merges the last two edges of the path, only the edge incident to the single merged vertex will be red, so this is a 1-sequence. Trees have twin-width at most two, and for some trees this is tight. A 2-contraction sequence for any tree may be found by choosing a root, and then repeatedly merging two leaves that have the same parent or, if this is not possible, merging the deepest leaf into its parent. The only red edges connect leaves to their parents, and when there are two at the same parent they can be merged, keeping the red degree at most two.[1]

More generally, the following classes of graphs have bounded twin-width, and a contraction sequence of bounded width can be found for them in polynomial time:

• Every graph of bounded clique-width, or of bounded rank-width, also has bounded twin-width. The twin-width is at most exponential in the clique-width, and at most doubly exponential in the rank-width.[1] These graphs include, for instance, the distance-hereditary graphs, the k-leaf powers for bounded values of k, and the graphs of bounded treewidth.
• Indifference graphs (equivalently, unit interval graphs or proper interval graphs) have twin-width at most two.[6]
• Unit disk graphs defined from sets of unit disks that cover each point of the plane a bounded number of times have bounded twin-width. The same is true for unit ball graphs in higher dimensions.[1]
• The permutation graphs coming from permutations with a forbidden permutation pattern have bounded twin-width. This allows twin-width to be applied to algorithmic problems on permutations with forbidden patterns.[1]
• Every family of graphs defined by forbidden minors has bounded twin-width. For instance, by Wagner's theorem, the forbidden minors for planar graphs are the two graphs ${\displaystyle K_{5}}$ and ${\displaystyle K_{3,3}}$, so the planar graphs have bounded twin-width.[1]
• Every graph of bounded stack number or bounded queue number also has bounded twin-width.[3] There exist families of graphs of bounded sparse twin-width that do not have bounded stack number, but the corresponding question for queue number remains open.[7]
• The strong product of any two graphs of bounded twin-width, one of which has bounded degree, again has bounded twin-width. This can be used to prove the bounded twin-width of classes of graphs that have decompositions into strong products of paths and bounded-treewidth graphs, such as the k-planar graphs.[3] For the lexicographic product of graphs, the twin-width is exactly the maximum of the widths of the two factor graphs.[8] Twin-width also behaves well under several other standard graph products, but not the modular product of graphs.[9]

In every hereditary family of graphs of bounded twin-width, it is possible to find a family of total orders for the vertices of its graphs so that the inherited ordering on an induced subgraph is also an ordering in the family, and so that the family is small with respect to these orders. This means that, for a total order on ${\displaystyle n}$ vertices, the number of graphs in the family consistent with that order is at most singly exponential in ${\displaystyle n}$. Conversely, every hereditary family of ordered graphs that is small in this sense has bounded twin-width.[4] It was originally conjectured that every hereditary family of labeled graphs that is small, in the sense that the number of graphs is at most a singly exponential factor times ${\displaystyle n!}$, has bounded twin-width.[3] However, this conjecture was disproved using a family of induced subgraphs of an infinite Cayley graph that are small as labeled graphs but do not have bounded twin-width.[10]

There exist graphs of unbounded twin-width within the following families of graphs:

• Graphs of bounded degree.[1]
• Interval graphs.[1]
• Unit disk graphs.[1]

In each of these cases, the result follows by a counting argument: there are more graphs of the given type than there can be graphs of bounded twin-width.[1]

If a graph has bounded twin-width, then it is possible to find a versatile tree of contractions. This is a large family of contraction sequences, all of some (larger) bounded width, so that at each step in each sequence there are linearly many disjoint pairs of vertices each of which could be contracted at the next step in the sequence. It follows from this that the number of graphs of bounded twin-width on any set of ${\displaystyle n}$ given vertices is larger than ${\displaystyle n!}$ by only a singly exponential factor, that the graphs of bounded twin-width have an adjacency labelling scheme with only a logarithmic number of bits per vertex, and that they have universal graphs of polynomial size in which each ${\displaystyle n}$-vertex graph of bounded twin-width can be found as an induced subgraph.[3]

The graphs of twin-width at most one can be recognized in polynomial time.[8] However, it is NP-complete to determine whether a given graph has twin-width at most four, and NP-hard to approximate the twin-width with an approximation ratio better than 5/4. Under the exponential time hypothesis, computing the twin-width requires time at least exponential in ${\displaystyle n/\log n}$, on ${\displaystyle n}$-vertex graphs.[11] In practice, it is possible to compute the twin-width of graphs of moderate size using SAT solvers.[12] For most of the known families of graphs of bounded twin-width, it is possible to construct a contraction sequence of bounded width in polynomial time.[1]

Once a contraction sequence has been given or constructed, many different algorithmic problems can be solved using it, in many cases more efficiently than is possible for graphs that do not have bounded twin-width. As detailed below, these include exact parameterized algorithms and approximation algorithms for NP-hard problems, as well as some problems that have classical polynomial time algorithms but can nevertheless be sped up using the assumption of bounded twin-width.