We give an O(√n log n)-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 stretch k ≥ 1, a subgraph H = (V,EH) is a k-spanner of G if for every edge (u, v) ∈ E, the graph H contains a path from u to v of length at most k ċ d(u, v). The previous best approximation ratio was O(n2/3), due to Dinitz and Krauthgamer (STOC '11).#R##N##R##N#We also present an improved algorithm for the important special case of directed 3-spanners with unit edge lengths. The approximation ratio of our algorithm is O(n1/3) which almost matches the lower bound shown by Dinitz and Krauthgamer for the integrality gap of a natural linear programming relaxation. The best previously known algorithms for this problem, due to Berman, Raskhodnikova and Ruan (FSTTCS '10) and Dinitz and Krauthgamer, had approximation ratio O(√n).
['Piotr Berman', 'Arnab Bhattacharyya', 'Konstantin Makarychev', 'Sofya Raskhodnikova', 'Grigory Yaroslavtsev']
Improved approximation for the directed spanner problem