2
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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