2
$\begingroup$

Given a graph $G$ with $n$ vertices, let $(X, T)$ be a tree decomposition of $G$ with the smallest width. Is the number of nodes in $T$ upper bounded by $n$? I have googled it but all materials I found discuss only treewidth.

$\endgroup$
1
$\begingroup$

Not a complete answer, but in T. Kloks Treewidth you have the following lemma:

There always exists a nice tree decomposition of width $k$ and with at most $4n$ bags.

It is NP-complete to determine the minimum number of bags in a tree decomposition of width $k$.

$\endgroup$
0
$\begingroup$

Take any node $X_1$ of your tree decomposition $T$. It contains at least 2 vertices from $G$. Let's call $T'_1 = \{X_1\}$, a new tree containing only this node. And $L_1$, the cardinality of the subset of $G$ it contains, thus $L_1 \ge 2.$

Then you add all the other nodes $X_i$ of $T$, one by one, to grow this new tree incrementing the index $i$ of $T'_i$ containing $L_i$ vertices of $G$. The only rule is to pick a node which is connected to $T'_i$, it is always possible as $T$ is connected.

Thus, the new node $X_i$ is connected to $T'_{i-1}$ by only one edge (either it would not be a tree anymore). Let's call $X_j$, the other node of this edge.

Then $X_i$ contains at least one vertex from $G$ which is not in $X_j$ and not in any other node of $T'_{i-1}$, because it would imply to put a new edge and not respect the tree statement. Then $L_i \ge L_{i-1} + 1$.

By induction you get $n \ge L_k \ge 1+k$, with $k$ the number of nodes in $T$.

Then the tree decomposition can have at most $n-1$ nodes

$\endgroup$
  • $\begingroup$ The first sentence is incorrect: It contains at least 2 vertices from $G$. A bag can contain one vertex. $\endgroup$ – Pål GD Apr 17 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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