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⊆V×V of ordered node pairs, and an integer k⩽|D|, find a minimum 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: O˜(k2/3) for k-DSF by Charikar et al. (1999) [6], and O(k1/2+ε) for DSF by Chekuri et al. (2008) [7]. Our main result is achieving the first sub-linear in terms of n=|V| approximation ratio for DSF. Specifically, we give an O(nε⋅min{n4/5,m2/3})-approximation scheme for DSF. For k-DSF we give a simple greedy O(k1/2+ε)-approximation algorithm. This improves upon the best known ratio O˜(k2/3) by Charikar et al. (1999) [6], and (almost) matches, in terms of k, the best ratio known for the undirected variant (Gupta et al., 2010 [18]). This algorithm uses a new structure called start-junction tree which may be of independent interest.