Let G = ( V , E ) be a graph with n nodes in which each pair of nodes is joined

Question

Let G = (V, E) be a graph with n nodes in which each pair of nodes is joined by an edge. There is a positive weight wij on each edge (i, j); and we will assume these weights satisfy the triangle inequality wik wij + wjk. For a subset V V, we will use G[V] to denote the subgraph (with edge weights) induced on the nodes in V. We are given a set X V of k terminals that must be connected by edges. We say that a Steiner tree on X is a set Z so that X Z V, together with a spanning subtree T of G[Z]. The weight of the Steiner tree is the weight of the tree T.

Show that the problem of finding a minimum-weight Steiner tree on X can be solved in time O(nO(k)).

Explanation / Answer

In a Steiner tree T on X Z V, |X| = k, we will refer to X as the terminals and Z as the extra nodes.

Proof.

We first claim that each extra node has degree at least 3 in T; for it not, then the triangle inequality implies we can replace its two incident edges by an edge joining its two neighbours.

Since the sum of the degrees in a t-node tree is 2t - 2, every tree has at least as many leaves as it has nodes of degree greater than 2.
Hence |Z| <= k.
It follows that if we compute the minimum spanning tree on all sets of the form X Z with |Z| <= k. the cheapest among these will be the minimum Steiner tree.
There are at most (n2k) = nO(k) such sets to try, so overall running time will be nO(k) .
.

THANK YOU.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.