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 × 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) k pairs (s, t) ∊ D. When k = |D|, we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: for k-DSF by Charikar et al. [2], and O(k1/2+∊) for DSF by Chekuri et al. [3]. For DSF we give an O(n∊.min{n4/5, m2/3})-approximation scheme using a novel LP-relaxation seeking to connect pairs via “cheap” paths. This is the first sub-linear (in terms of n = |V|) approximation ratio for the problem. For k-DSF we give a simple greedy O(k1/2+∊)-approximation scheme, improving the best known ratio 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.