Parallel Greedy Spanners

Abstract

A $t$-spanner of a graph is a subgraph that $t$-approximates pairwise distances. The greedy algorithm is one of the simplest and most well-studied algorithms for constructing a sparse spanner: it computes a $t$-spanner with $n^{1+O(1/t)}$ edges by repeatedly choosing any edge which does not close a cycle of chosen edges with $t+1$ or fewer edges. We demonstrate that the greedy algorithm computes a $t$-spanner with $t^3\cdot {\log }^{3}n\cdot n^{1+O(1/t)}$ edges even when a matching of such edges are added in parallel. In particular, it suffices to repeatedly add any matching where each individual edge does not close a cycle with $t+1$ or fewer edges but where adding the entire matching might. Our analysis makes use of and illustrates the power of new advances in length-constrained expander decompositions.