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.
3
$\begingroup$
$\endgroup$
2
$\begingroup$
$\endgroup$
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$.
0
$\begingroup$
$\endgroup$
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
-
$\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
