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.