Finding sparser directed spanners

A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, a subgraph H = (V,E _H) is a k-spanner of a graph G = (V,E) if for every pair of vertices u, v ∈ V, the shortest path distance dist_H(u,v) from u to v in H is at most k · distc(u, v). We focus on spanners of directed graphs and a related notion of transitive-closure spanners. The latter captures the idea that a spanner should have a small diameter but preserve the connectivity of the original graph. We study the computational problem of finding the sparsest k-spanner (resp., k-TC-spanner) of a given directed graph, which we refer to as DIRECTED k-SPANNER (resp., k-TC-SPANNER). We improve all known approximation algorithms for DIRECTED k-SPANNER and k-TC-SPANNER for k ≥ 3. (For k = 2, the current ratios are tight, assuming P≠NP.) Along the way, we prove several structural results about the size of the sparsest spanners of directed graphs.