Making a minimum-width tree decomposition lean in polynomial time
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&#39;$. A min-width tree-decomposition of $G&#39;$ 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$.