HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Size of tree decomposition

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#107036, answer score: 3

Revisions (0)

No revisions yet.