Improved approximating 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 ⊆ V x V of ordered node pairs, and an integer k ≤ |D|, find a min-cost subgraph H of G that contains an st-path for (at least) kc pairs (s, t) ∈ D. When k = |D|, we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: Õ(k ^2/3) for k-DSF by Charikar et al. [2], and O(k ^1/2+ε) for DSF by Chekuri et al. [3]. For DSF we give an O(n ^ε·mm{n ^4/5, m ^2/3})-approximation scheme using a novel LP-relaxation seeking to connect pairs via "cheap" paths. This is the first sublinear (in terms of n = |V|) approximation ratio for the problem. For k-DSF we give a simple greedy O(k ^1/2+ε)-approximation scheme, improving the best known ratio Õ(k ^2/3) by Charikar et al. [2], and (almost) matching, in terms of k, the best ratio known for the undirected variant [11]. Even when used for the particular case DSF, our algorithm favorably compares to the one of [3], which repeatedly solves linear programs, and uses complex time and space consuming transformations.