# Approximate minimum-weighted tree decomposition on complete graphs

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?

• 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? – user742 May 2 '12 at 23:09
• 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? – Joe May 3 '12 at 6:11
• 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. – Geni May 3 '12 at 20:13
• I see. The height of the tree must be exactly $h$, not upper bounded by $h$. I guess I misread your question. – Joe May 3 '12 at 20:16
• You might try cross-posting this as a reference request on cstheory (with a link back to this question of course). – Joe May 3 '12 at 20:19