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?

  • 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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.