In graph theory, a bramble for an undirected graphG is a family of connectedsubgraphs of G that all touch each other: for every pair of disjoint subgraphs, there must exist an edge in G that has one endpoint in each subgraph. The order of a bramble is the smallest size of a hitting set, a set of vertices of G that has a nonempty intersection with each of the subgraphs. Brambles may be used to characterize the treewidth of G.
Treewidth and havens
A haven of order k in a graph G is a function β that maps each set X of fewer than k vertices to a connected component of G − X, in such a way that every two subsetsβ and β touch each other. Thus, the set of images of β forms a bramble in G, with order k. Conversely, every bramble may be used to determine a haven: for each set X of size smaller than the order of the bramble, there is a unique connected component β that contains all of the subgraphs in the bramble that are disjoint from X. As Seymour and Thomas showed, the order of a bramble characterizes treewidth: a graph has a bramble of order kif and only if it has treewidth at least.
Size of brambles
s of bounded degree have treewidth proportional to their number of vertices, and therefore also have brambles of linear order. However, as Martin Grohe and Dániel Marx showed, for these graphs, a bramble of such a high order must include exponentially many sets. More strongly, for these graphs, even brambles whose order is slightly larger than the square root of the treewidth must have exponential size. However, Grohe and Marx also showed that every graph of treewidth k has a bramble of polynomial size and of order.
Computational complexity
Because brambles may have exponential size, it is not always possible to construct them in polynomial time for graphs of unbounded treewidth. However, when the treewidth is bounded, a polynomial time construction is possible: it is possible to find a bramble of order k, when one exists, in time O where n is the number of vertices in the given graph. Even faster algorithms are possible for graphs with few minimal separators. Bodlaender, Grigoriev, and Koster studied heuristics for finding brambles of high order. Their methods do not always generate brambles of order close to the treewidth of the input graph, but for planar graphs they give a constantapproximation ratio. Kreutzer and Tazari provide randomized algorithms that, on graphs of treewidth k, find brambles of polynomial size and of order within polynomial time, coming within a logarithmic factor of the order shown by to exist for polynomial size brambles.
Directed brambles
The concept of bramble has also been defined for directed graphs. In a directed graphD, a bramble is a collection of strongly connected subgraphs of D that all touch each other: for every pair of disjoint elements X, Y of the bramble, there must exist an arc in D from X to Y and one from Y to X. The order of a bramble is the smallest size of a hitting set, a set of vertices of D that has a nonempty intersection with each of the elements of the bramble. The bramble number of D is the maximum order of a bramble in D. The bramble number of a directed graph is within a constant factor of its directed treewidth.
