As is well known, a tree decomposition of a graph $G$ consists of a tree $T$ with an associated bag $T_v \subseteq V(G)$ for each vertex $v \in V(T)$, which satisfies the following conditions:Every vertex of $G$ occurs in some bag of $T$.For every edge of $G$ there is a bag containing both endpoints of the edge.For every vertex $v \in V(G)$, the bags containing $v$ induce a connected subtree of $T$.We may also demand the following condition, called leanness, from our decomposition:For every pair of bags $T_a$, $T_b$ of $T$, if $A \subseteq T_a$ and $B \subseteq T_b$ with $|A| = |B| = k$, then either a) there are $k$ vertex-disjoint $A-B$ paths in $G$, or b) the tree $T$ contains an edge $pq$ on the path from node $a$ to node $b$ such that $|V(T_p) \cap V(T_q)| \leq k$ and the set $V(T_p) \cap V(T_q)$ intersects all $A-B$ paths in $G$.Robin Thomas showed that there is always a minimum-width tree decomposition which is also lean, and simpler proofs of this fact have been provided by several authors, for example by Patrick Bellenbaum & Reinhard Diestel.What I am interested in is the following: given a graph $G$ and a  minimum-width tree decomposition of $G$, can we find a minimum-width  lean tree decomposition of $G$ in polynomial time?The two mentioned proofs do not yield such efficient constructiveness. In the paper of Bellenbaum and Diestel it is mentioned that Another (more constructive) short proof of Thomass theorem has been given in P. Bellenbaum, Schlanke Baumzerlegungen von Graphen, Diplomarbeit, Universitat Hamburg 2000. Alas, I have not been able to find the manuscript online and my German is not that great.
Making a minimum-width tree decomposition lean in polynomial time
ds.algorithms;graph theory;graph algorithms;treewidth
Here is a formal reason why the problem is not poly-time solvable unless P=NP. We know that finding the treewidth of a given graph is NP-Hard. Given a graph $G$ we can add a disjoint clique of size $V(G)+1$ to create a new graph $G'$. A min-width tree-decomposition of $G'$ can be obtained as follows: it has two nodes with one bag containing all the nodes of the clique and the other containing all the nodes of $G$. Now making this tree-decomposition lean would require finding a lean-tree decomposition of the original graph $G$ which would, as a by-product, give the treewidth of $G$.