Question

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?

Answer 1

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.