Improved Approximation for the Directed Spanner Problem

Arnab Bhattacharyya, Konstantin Makarychev

We prove that the size of the sparsest directed k-spanner of a graph can be approximated in polynomial time to within a factor of $\tilde{O}(\sqrt{n})$, for all k >= 3. This improv…