patternMinor
Size of tree decomposition
Viewed 0 times
decompositionsizetree
Problem
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.
Solution
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$.
At request of references:
Lemma 2.2. Every graph $G$ with treewidth $k$ has a nice tree-decomposition of width $k$. Furthermore, if $n$ is the number of vertices of $G$ then there exists a nice tree-decomposition with at most $4n$ nodes.
Bodlaender, H.L. and Kloks, T. (1996) "Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs", Journal of Algorithms, 21(2), pp. 358–402. Available at: https://doi.org/10.1006/jagm.1996.0049.
They don't give a proof, but reference Kloks, T. (ed.) (1994) Treewidth. Berlin/Heidelberg: Springer-Verlag (Lecture Notes in Computer Science). Available at: https://doi.org/10.1007/BFb0045375.
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$.
At request of references:
Lemma 2.2. Every graph $G$ with treewidth $k$ has a nice tree-decomposition of width $k$. Furthermore, if $n$ is the number of vertices of $G$ then there exists a nice tree-decomposition with at most $4n$ nodes.
Bodlaender, H.L. and Kloks, T. (1996) "Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs", Journal of Algorithms, 21(2), pp. 358–402. Available at: https://doi.org/10.1006/jagm.1996.0049.
They don't give a proof, but reference Kloks, T. (ed.) (1994) Treewidth. Berlin/Heidelberg: Springer-Verlag (Lecture Notes in Computer Science). Available at: https://doi.org/10.1007/BFb0045375.
Context
StackExchange Computer Science Q#107036, answer score: 3
Revisions (0)
No revisions yet.