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, 2012 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, 2012 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, 2012 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, 2012 at 20:16

This problem does not admit even a constant-factor polynomial time approximation algorithm, unless P = NP.

Proof: Assume there exists a polynomial time $$\alpha$$-approximation algorithm $$A$$ for this problem. Consider the following reduction from Hamiltonian path:

Given an unweighted undirected graph $$G$$ as input. Give every edge weight $$1$$. Now complete the graph by adding dummy edges between every pair of vertices with weight $$|V| \cdot \alpha$$. Call this graph $$H$$.

Now, if $$G$$ admits a Hamiltonian path then the minimum $$(1, |V| - 1)$$ decomposition of $$H$$ has weight exactly $$|V| - 1 \implies A(H) \leq \alpha \cdot (|V| - 1)$$.

On the other hand, if $$G$$ does not admit a Hamiltonian path then the minimum $$(1, |V|-1)$$ decomposition of $$H$$ has weight $$\geq |V| \cdot \alpha > \alpha \cdot (|V| - 1)$$.

Therefore, $$G$$ admits a Hamiltonian path if and only if $$A(H) \leq \alpha \cdot (|V| - 1)$$.

This is the exact proof for why it is NP-Hard to approximate the Travelling Salesman Problem within a constant factor.