Steiner Forest exemplary search algorithm

Question

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

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

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

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

Sufficient theory. Finding such a forest with minimal weight is difficult (NP-complete). Do you know a faster approximate search algorithm for such a forest with suboptimal weight?

Answer 1

Chapter 20 of the Vijaya Wazirani approximation algorithms describes the Steiner forest generation scheme. The analysis uses the LP duality, which it uses to determine the coefficient of the algorithm:

(This is a factor 2 algorithm, but in practice it probably works pretty well)

Application Algorithms

Also: see note in 22.5, which describes three documents for further reading, including an overview of the topic.

Answer 2

Maybe you can reformulate this problem as another NP-complete one for which you know any suboptimal algorithms? This is just an assumption, but I cannot find such a mapping with my very limited math skills :)