An approximate algorithm for finding Steiner Forest.

Question

Hello.

Consider a weighted graph G=(V,E,w). We are given a family of subsets of vertices V_i.

A Steiner Forest is a forest that for each subset of vertices V_i connects all of the vertices in this subset with a tree.

Example: only one subset V_1 = V. In this case a Steiner forest is a spanning tree of the whole graph.

Example: a graph P4 (path with 4 vertices) and two subsets: V_1 = {v1, v4} and V_2 = {v2, v3}. The Steiner tree for this example is the whole graph.

Enough theory. Finding such a forest with minimal weight is difficult (NP-complete). Do you know any quicker approximate algorithm to find such a forest with non-optimal weight?

Answer 1

Maybe you can restate this problem as other NP-complete, for which you know any suboptimal algorithms? This is just a guess, though -- I can't find such mapping with my very limited math skills :)

Answer 2

Chapter 20 of Approximation Algorithms by Vijay Vazirani describes a schema for generating a Steiner Forest. The analysis uses LP-duality, which he uses to determine the factor of the algorithm:

(This is a factor-2 algorithm but in practice it probably fares quite well)

Approximation Algorithms

Also: see the note in 22.5 that describes three papers for further reading, including a survey of the topic.