Tangles are decided by weighted vertex sets

Tree-like decompositions play an important role both in structural combinatorics and algorithm design. The most well-known are tree decompositions of graphs, which are of key importance in the Graph Minor Project of Robertson and Seymour as well as in algorithm design. The minimum width of a tree decomposition is the treewidth of a graph; this parameter captures how closely the global structure of a graph resembles a tree. In particular, a graph has treewidth one if and only if each of its components is a tree. Treewidth has a strong duality property in the sense of mathematical optimization: the minimum treewidth of a graph is equal to the maximum order of a bramble increased by one; a bramble is a collection of touching connected subgraphs that cannot be hit by a small set of vertices.

Branchwidth, which is linearly related to treewidth, is another important width parameter, and its dual parameter is the maximum order of a tangle, an object that is more amenable to generalizations to other combinatorial structures than a bramble. Informally speaking, a tangle picks for every separation a small part in a way that small parts of any three separations do not cover the whole structure. In the case of graphs, a tangle of order $k$ concerns vertex $k$-separations, i.e., pairs of subsets of the vertex set such that the union of the two subsets is the whole vertex set, the intersection has size at most $k$ and every edge is in one of the subsets. The main result of the article asserts that every tangle of a graph can be obtained by assigning weights to the vertices so that the small part of every $k$-separation is the one of smaller weight.