Intuitively, it measures how similar the graph is to a cograph, a type of graph that can be reduced to a single vertex by repeatedly merging together twins, vertices that have the same neighbors.
The twin-width is defined from a sequence of repeated mergers where the vertices are not required to be twins, but have nearly equal sets of neighbors.
Twin-width is defined for finite simple undirected graphs.
[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.
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.
For a family of graphs that is closed under taking induced subgraphs and has bounded twin-width, the following properties are equivalent:[3] Such a family is said to have bounded sparse twin-width.
[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.
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.
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.
[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: 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.
vertices, the number of graphs in the family consistent with that order is at most singly exponential in
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
[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.
[1] If a graph has bounded twin-width, then it is possible to find a versatile tree of contractions.
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
-vertex graph of bounded twin-width can be found as an induced subgraph.
[11] In practice, it is possible to compute the twin-width of graphs of moderate size using SAT solvers.
[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.
This style of analysis is generally applied to problems that do not have a known polynomial-time algorithm, because otherwise fixed-parameter tractability would be trivial.
Many such problems have been shown to be fixed-parameter tractable with twin-width as a parameter, when a contraction sequence of bounded width is given as part of the input.
This applies, in particular, to the graph families of bounded twin-width listed above, for which a contraction sequence can be constructed efficiently.
This is in contrast to more general graphs, for which it is NP-hard to obtain an approximation ratio that is better than logarithmic.
In contrast, without the assumption of bounded twin-width, it is NP-hard to achieve any approximation ratio of this form with