Can a bramble of maximal order be efficiently found from a tree decomposition of minimal width?

Question

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.

Answer 1

Chapelle et al. gave an algorithm that in $O(n^{k+4})$ constructs a bramble of order $k+2$ knowing that the graph has tree-width larger than $k$, here is the link to their report: https://www.univ-orleans.fr/lifo/Members/todinca/PS/brambles.pdf

They provided a straight forward pseudo code for their algorithm. In general, as proven in https://www.sciencedirect.com/science/article/pii/S0095895608000683 by Grohe and Marx, there exists a class of graphs $(G_k)_{k\geq 1}$ such that:

• $|V(G_k)| = O(k)$ and $|E(G_k)|=O(K)$ for $k\geq 1$;

• $tw(G_k)\geq k$ for every $k\geq 1$;

• for every $\epsilon>0$ and $k\geq 1$ every bramble of $G_k$ of order $k^{1/2+\epsilon}$ has size at least $2^{\Omega(K)}$.

This basically means that there are some graphs for which a bramble should be relatively big to have the right bramble order. As a classic result, we know that for a graph $G$ with $tw(G) = k$ there exists a nice tree decomposition of width $k$ and size at most $4n$ where $n$ is the number of vertices(this is proven in "Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs" by Bodlaender and Kloks). Putting these together we can observe that it is not possible to construct a bramble of right order having the tree-width or even a good tree decomposition efficiently. Chapelle et al. also point out that as the object they are about to construct has size $\Omega(n^{k+1})$ we can not except a drastically better algorithm in the sense of efficiency.