Hello.


Background
----------


Consider a weighted graph $G=(V,E,w)$. We are given a family of $k$ disjoint subsets of vertices $V\_1, \cdots, V\_k$.


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 of vertices $V\_1 = V$. In this case a Steiner forest is a spanning tree of the whole graph.


Question
--------



> 
> 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?
> 
> 
> 



An approximate algorithm for finding Steiner Forest in a graph.
There is a 2-approximation algorithm, see e.g. 



> 
> A General Approximation Technique For Constrained Forest Problems, Michel Goemans, David P. Williamson, SIAM Journal on Computing 1992.
> 
> 
> 


For special kind of graphs, better bounds can be obtained: for planar graphs there is a PTAS,



> 
> Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx, STOC '10.
> 
> 
> 


