The Steiner tree problem is the following: Input: An undirected graph G = ( V ,

Question

The Steiner tree problem is the following:

Input: An undirected graph G = (V, E ) with non-negative edge weights wt : E N, a set S V of special nodes.

Output: A Steiner tree for S whose total weight is minimal

A Steiner tree for S is a tree composed of edges from G that spans (connects) all of the special nodes S. In other words, a Steiner tree is a subset E E of edges, such that for every s,t S, there is a path from s to t using only edges from E. The total weight of the Steiner tree is the sum of the weights included in the tree, i.e., eE wt(e).

The Steiner tree problem has many applications in different areas, including creating genealogy trees to represent the evolutionary tree of life, designing efficient networks, to even planning water pipes or heating ducts in buildings. Unfortunately, it is NP-hard.

An approximation algorithm for this problem:

Compute the shortest distance between all pairs of special nodes. Use these distances to create a modified and complete graph G = (S,ES), which uses the special nodes as vertices, and the weight of the edge between two vertices is the shortest distance between them.

Find the minimal spanning tree of G. Call it M.

Reinterpret M to give us a Steiner tree for G: for edge in M, say an edge (r,s), select the edges in G that correspond to the shortest path from r to s. Put together all the selected edges to get a Steiner tree.

Prove that this algorithm achieves an approximation ratio of 2.

Note that the efficiency of an approximation algorithm does not contradict NP-completeness because it gives an approximate (rather than an exact) solution to the problem.

Hint: Given the minimal-weight Steiner tree for G, construct a tour in G that visits each special vertex of G at least once. See if you can figure out how the following four quantities relate to each other: (a) the total weight of the minimal Steiner tree, (b) the total weight of this tour, (c) the weight of M, (d) the total weight of the Steiner tree output by the above approximation algorithm.

Explanation / Answer

Consider an instance in which for S={v0}, R={v1,..,vn},d={v0,vi}=1,for i=1,...,n and d{vi,vj}=2  and for all 1<=i<=j<=n. That is, consider an instance in which the required points are all at distance two from each other, but they are all at distance one from the unique optional point. Then the minimum Steiner tree has v0 as a root and the nodes v1,..vn  as leaves, and it has cost n but the minimum spanning tree of R has cost 2n-2  because it is a tree with n nodes and n-1  edges, and each edge is of cost 2.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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