Let $G$ be a connected graph with vertices $V(G)$. A bramble of $G$ is a set of connected subgraphs $H_1,\ldots,H_n$ such that for each $i$ and $j$, $H_i$ touches $H_j$; that is, either $H_i$ intersects $H_j$ in a vertex, or there is an edge in $G$ that connects a vertex of $H_i$ to a vertex of $H_j$. The order of a bramble is the minimum size of a set $S\subset V(G)$ such that $S\cap H_i$ is nonempty for all ??.

It was shown by Seymour and Thomas (in "Graph Searching and a Min-Max Theorem for Tree-Width") that $G$ has tree-width at least $k-1$ if and only if and only if $G$ has a bramble of order at least $k$. Suppose we know that a graph has tree-width equal to $k-1$. Are there any computational tools out there to find a bramble of order $k$? (I am happy to assume that we have an explicit tree decomposition of width $k-1$, if this is useful for finding the bramble.)

There are certainly papers that present algorithms for finding such brambles (e.g. "A Branch-and-Price-and-Cut Method for Computing an Optimal Bramble" by Sonuc, Smith and Hicks); I am interested in actual implementations that are available.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.