Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By $(d, h)$-tree-decomposition, I mean to divide the vertices $V$ into $k$ trees, such that the height of each tree is $h$, and each non-leaf node has $d$ children.

I know it is definitely $\text{NP}$-Hard, since minimum $(1, |V|-1)$-tree-decomposition is the minimum Hamilton path. But are there any good approximation algorithms?


migrated from stackoverflow.com May 2 '12 at 21:47

This question came from our site for professional and enthusiast programmers.

  • 2
    $\begingroup$ It seems to be hard even for simple graphs, What's the usage of this decomposition? We have lots of well-known decomposition techniques, but they all have a usage in some problems, but what do you want to do with this sort of decomposition? $\endgroup$ – user742 May 2 '12 at 23:09
  • $\begingroup$ It's not necessarily a Hamiltonian path. In particular, the solution might be a star-graph. Isn't $(1, |V| - 1)$ just the minimum spanning tree? $\endgroup$ – Joe May 3 '12 at 6:11
  • $\begingroup$ Hi @Joe . Sorry, I did not state it clearly. (1, |V|-1) has to be a path rather than a star, because each node has one child and the height of the tree is |V|-1. $\endgroup$ – Geni May 3 '12 at 20:13
  • $\begingroup$ I see. The height of the tree must be exactly $h$, not upper bounded by $h$. I guess I misread your question. $\endgroup$ – Joe May 3 '12 at 20:16
  • $\begingroup$ You might try cross-posting this as a reference request on cstheory (with a link back to this question of course). $\endgroup$ – Joe May 3 '12 at 20:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.