<p>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$.</p>

CC BY-SA 3.0
2011-12-05T08:54:22.093Z
Good point. Do you know if anything is known about parameterized and / or moderately exponential time algorithms for finding lean tree decompositions?
Bart Jansen
CC BY-SA 3.0
2011-12-04T21:21:55.833Z
2011-12-04T21:21:55.833Z
Chandra Chekuri
<p>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:</p>

<ol>
<li>Every vertex of $G$ occurs in some bag of $T$.</li>
<li>For every edge of $G$ there is a bag containing both endpoints of the edge.</li>
<li>For every vertex $v \in V(G)$, the bags containing $v$ induce a connected subtree of $T$.</li>
</ol>

<p>We may also demand the following condition, called <em>leanness</em>, from our decomposition:</p>

<ul>
<li>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$.</li>
</ul>

<p><a href="http://www.sciencedirect.com/science/article/pii/009589569090130R">Robin Thomas</a> 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 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.1355">Patrick Bellenbaum &amp; Reinhard Diestel</a>.</p>

<blockquote>
  <p>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
  <em>lean</em> tree decomposition of $G$ in polynomial time?</p>
</blockquote>

<p>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 Thomas’s 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.</p>

CC BY-SA 3.0
2011-12-02T16:33:29.100Z
Nice question. Finding a minimum-width tree decomposition is NP-Hard so your problem is somewhat ill-posed (it appears). My guess would be that one can ask this for bounded treewidth case or in the approximation sense.
Chandra Chekuri
CC BY-SA 3.0
2011-12-02T17:44:42.513Z
But in his case he's *given* a min-width tree decomposition and he wants an algorithm to make it lean.
Suresh Venkat
CC BY-SA 3.0
2011-12-02T19:00:47.250Z
@SureshVenkat: I realize that he is given a min-width tree decomposition but how can you even verify that it is correct? Moreover, a lean tree decomposition adapts locally to the treewidth of different parts of the graph so having a tree decomposition of the global graph which is optimal does not avoid the problem of finding treewidth of the local pieces which is hard.
Chandra Chekuri
CC BY-SA 3.0
2011-12-02T20:03:41.593Z
*Smooth* tree decompositions (where all bags have the same size and two adjacent bags differ by exactly one vertex) are much easier to handle than general tree decompositions, and it is easy to see that there is always a minimum-width tree decomposition which is smooth.
So maybe you can get an efficient construction by restricting one of the known constructions to these. Does there always exist a minimum-width tree decomposition which is smooth and lean?
didest
CC BY-SA 3.0
2011-12-02T20:37:30.167Z
@ChandraChekuri I assume the verification issue goes away if you phrase it as a promise problem, but I see your point about having one tree decomposition not necessarily giving you enough info to adapt. But the following question might be plausible: is there a way to "locally" modify a given tree decomposition to make it "lean" without increasing the treewidth ?
Suresh Venkat
<ds.algorithms><graph-theory><graph-algorithms><treewidth>
Making a minimum-width tree decomposition lean in polynomial time
Bart Jansen
# Making a minimum-width tree decomposition lean in polynomial time

(Asked by: username_0 on 2011-12-02)

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:

1. Every vertex of $G$ occurs in some bag of $T$.
2. For every edge of $G$ there is a bag containing both endpoints of the edge.
3. 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](http://www.sciencedirect.com/science/article/pii/009589569090130R) 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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.1355).

> 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 Thomas’s 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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, treewidth

> **Comments:**
> **username_1**: Nice question. Finding a minimum-width tree decomposition is NP-Hard so your problem is somewhat ill-posed (it appears). My guess would be that one can ask this for bounded treewidth case or in the approximation sense.  
> **username_2**: But in his case he's *given* a min-width tree decomposition and he wants an algorithm to make it lean.  
> **username_1**: @SureshVenkat: I realize that he is given a min-width tree decomposition but how can you even verify that it is correct? Moreover, a lean tree decomposition adapts locally to the treewidth of different parts of the graph so having a tree decomposition of the global graph which is optimal does not avoid the problem of finding treewidth of the local pieces which is hard.  
> **username_3**: *Smooth* tree decompositions (where all bags have the same size and two adjacent bags differ by exactly one vertex) are much easier to handle than general tree decompositions, and it is easy to see that there is always a minimum-width tree decomposition which is smooth. So maybe you can get an efficient construction by restricting one of the known constructions to these. Does there always exist a minimum-width tree decomposition which is smooth and lean?  
> **username_2**: @ChandraChekuri I assume the verification issue goes away if you phrase it as a promise problem, but I see your point about having one tree decomposition not necessarily giving you enough info to adapt. But the following question might be plausible: is there a way to "locally" modify a given tree decomposition to make it "lean" without increasing the treewidth ?  

---

## 1 answers

### Answer by username_1 on 2011-12-04. Score: 8 | Accepted answer

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$.

> **Comments:**
> **username_0**: Good point. Do you know if anything is known about parameterized and / or moderately exponential time algorithms for finding lean tree decompositions?  

---

