Tech Report CS-93-42

A Primal-Dual Approximation Algorithm for the Steiner Forest

R. Ravi

September 1993

Abstract:

Given an undirected graph with nonnegative edge-costs, a subset of nodes of size $k$ called the terminals, and an integer $q$ between 1 and $k$, the minimum $q$-Steiner forest problem is to find a forest of minimum cost with at most $q$ trees that spans all the terminals. When $q = 1$, we have the classical minimum-cost Steiner tree problem on networks. In this note, we adapt a primal-dual approximation algorithm for the latter problem due to Agrawal, Klein and Ravi to provide one for the former. The algorithm runs in time $O( n \log n + m)$ and outputs a solution of cost at most $2(1 - \frac{1}{k-q+1})$ times the minimum. Here $n$ and $m$ denote respectively the number of nodes and edges in the input graph.

(complete text in pdf or gzipped postscript)