An approximate algorithm for finding Steiner Forest in a graph. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T02:09:15Z http://mathoverflow.net/feeds/question/21859 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/21859/an-approximate-algorithm-for-finding-steiner-forest-in-a-graph An approximate algorithm for finding Steiner Forest in a graph. Tadeusz A. Kadłubowski 2010-04-19T17:17:01Z 2010-04-19T17:50:43Z <p>Hello.</p> <h2>Background</h2> <p>Consider a weighted graph \$G=(V,E,w)\$. We are given a family of \$k\$ disjoint subsets of vertices \$V_1, \cdots, V_k\$.</p> <p>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.</p> <p>Example: only one subset of vertices \$V_1 = V\$. In this case a Steiner forest is a spanning tree of the whole graph.</p> <h2>Question</h2> <blockquote> <p>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?</p> </blockquote> http://mathoverflow.net/questions/21859/an-approximate-algorithm-for-finding-steiner-forest-in-a-graph/21865#21865 Answer by Hsien-Chih Chang for An approximate algorithm for finding Steiner Forest in a graph. Hsien-Chih Chang 2010-04-19T17:50:43Z 2010-04-19T17:50:43Z <p>There is a 2-approximation algorithm, see e.g. </p> <blockquote> <p>A General Approximation Technique For Constrained Forest Problems, Michel Goemans, David P. Williamson, SIAM Journal on Computing 1992.</p> </blockquote> <p>For special kind of graphs, better bounds can be obtained: for planar graphs there is a PTAS,</p> <blockquote> <p>Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx, STOC '10.</p> </blockquote>