1
$\begingroup$

Fix a parameter D and let the $D$-treewidth be the minimum width among tree-decompositions of H where the underlying tree has height D.

We know:

Can we say something in general about D-treewidth? In particular, how does $D$-treewidth decrease as we increase $D$.

$\endgroup$

1 Answer 1

1
$\begingroup$

One way to address this question is to think of a tree decomposition as an unrooted tree. Then, it is easy to see that its diameter is related to the depth by a factor of 2. Searching for diameter, instead of depth, may help you find more related results.

In this paper by Bodlaender and Hagerup, for example, they do something which sounds like the inverse function of what you want: they determine some pretty good bounds on the minimum diameter necessary in a decomposition of a graph of treewidth $k$, if you allow bags to have width $K > k$.

$\endgroup$

Your Answer

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

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