MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top



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.


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?

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.