Abstract:
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 \cite{GHNR}. 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.