Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-120 | 5th October 2007 00:00

Improved approximation algorithms for directed Steiner forest



We consider the k-Directed Steiner Forest} (k-dsf) problem:
given a directed graph G=(V,E) with edge costs, a collection D subseteq V \times V
of ordered node pairs, and an integer k leq |D|, find a minimum cost subgraph
H of G
that contains an st-path for (at least) k pairs (s,t) \in D.
When k=|D|, we get the Directed Steiner Forest dsf problem.
The best known approximation ratios for these problems are:
tilde O(k^{2/3}) for k-dsf by Charikar et.~al \cite{CCC}, and
O(k^{1/2 + epsilon) for dsf by Chekuri et.~al \cite{CEGS}.
We improve these approximation ratios as follows.

For dsf we give an tilde O(n^{4/5 + \epsilon)-approximation scheme
using a novel LP-relaxation that seeks to connect pairs with ''cheap'' paths.
This is the first sub-linear (in terms of n=|V|) approximation ratio for the problem;
all previous algorithm had ratio Omega(n^{1+epsilon}).

For k-dsf we give a simple greedy O(k^{1/2 + epsilon})-approximation algorithm.
This improves the best known ratio \tilde O(k^{2/3}) by Charikar et. al \cite
{CCC}, and
(almost) matches in terms of k the best ratio known for the undirected variant
Even when used for the particular case of dsf, our algorithm favorably compares
to the one of \cite{CEGS}, which repeatedly solves linear programs
and uses complex space and time consuming transformations.
Our algorithm is much simpler and faster, since it essentially reduces k-dsf
to a variant of the Directed Steiner Tree problem.
The simplification is due to a new notion of ``junction star-tree'' -- a union of an in-star
and an out-branching having the same root, which is of independent interest.

ISSN 1433-8092 | Imprint