Approximation algorithms for spanner problems and Directed Steiner Forest

• Published in: Information and computation 2013-01, Vol.222, p.93-107
• Main Authors: Berman, Piotr, Bhattacharyya, Arnab, Makarychev, Konstantin, Raskhodnikova, Sofya, Yaroslavtsev, Grigory
• Format: Article
• Language: English
• ISSN: 0890-5401; 1090-2651
• DOI: 10.1016/j.ic.2012.10.007

We present an O(nlogn)-approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, given a graph G=(V,E) with nonnegative edge lengths d:E→R⩾0 and a stretchk⩾1, a subgraph H=(V,EH) is a k-spanner of G if for every edge (s,t)∈E, the graph H contains a path from s to t of length at most k⋅d(s,t). The previous best approximation ratio was O˜(n2/3), due to Dinitz and Krauthgamer (STOC ʼ11). We also improve the approximation ratio for the important special case of directed 3-spanners with unit edge lengths from O˜(n) to O(n1/3logn). The best previously known algorithms for this problem are due to Berman, Raskhodnikova and Ruan (FSTTCS ʼ10) and Dinitz and Krauthgamer. The approximation ratio of our algorithm almost matches Dinitz and Krauthgamerʼs lower bound for the integrality gap of a natural linear programming relaxation. Our algorithm directly implies an O(n1/3logn)-approximation for the 3-spanner problem on undirected graphs with unit lengths. An easy O(n)-approximation algorithm for this problem has been the best known for decades. Finally, we consider the Directed Steiner Forest problem: given a directed graph with edge costs and a collection of ordered vertex pairs, find a minimum-cost subgraph that contains a path between every prescribed pair. We obtain an approximation ratio of O(n2/3+ϵ) for any constant ϵ>0, which improves the O(nϵ⋅min(n4/5,m2/3)) ratio due to Feldman, Kortsarz and Nutov (JCSSʼ12).