1
$\begingroup$

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.

$\endgroup$

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.