16
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Dec 2, 2011 at 16:33
  • 1
    $\begingroup$ But in his case he's given a min-width tree decomposition and he wants an algorithm to make it lean. $\endgroup$
    – Suresh Venkat
    Dec 2, 2011 at 17:44
  • 1
    $\begingroup$ @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. $\endgroup$
    – Chandra Chekuri
    Dec 2, 2011 at 19:00
  • $\begingroup$ 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? $\endgroup$
    – didest
    Dec 2, 2011 at 20:03
  • 1
    $\begingroup$ @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 ? $\endgroup$
    – Suresh Venkat
    Dec 2, 2011 at 20:37

1 Answer 1

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Good point. Do you know if anything is known about parameterized and / or moderately exponential time algorithms for finding lean tree decompositions? $\endgroup$
    – Bart Jansen
    Dec 5, 2011 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.