22
$\begingroup$

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?

$\endgroup$
4
  • 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, 2012 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, 2012 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, 2012 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, 2012 at 20:16

1 Answer 1

1
$\begingroup$

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.

$\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.