Near-Optimal Spanners for General Graphs in (Nearly) Linear Time

Abstract

Let $G=(V,E,w)$ be a weighted undirected graph on $|V|=n$ vertices and $|E|=m$ edges, let $k\ge 1$ be any integer, and let $\epsilon <1$ be any parameter. We present the following results on fast constructions of spanners with near-optimal sparsity and lightness, which culminate a long line of work in this area. (By near-optimal we mean optimal under Erdős' girth conjecture and disregarding the $\epsilon$-dependencies.) - There are (deterministic) algorithms for constructing $(2k-1)(1+\epsilon )$-spanners for $G$ with a near-optimal sparsity of $O(n^{1/k}\log (1/\epsilon )/\epsilon ))$. The first algorithm can be implemented in the pointer-machine model within time $O(m\alpha (m,n)\log (1/\epsilon )/\epsilon )+SORT(m))$, where $\alpha (,)$ is the two-parameter inverse-Ackermann function and $SORT(m)$ is the time needed to sort $m$ integers. The second algorithm can be implemented in the WORD RAM model within time $O(m\log (1/\epsilon )/\epsilon ))$. - There is a (deterministic) algorithm for constructing a $(2k-1)(1+\epsilon )$-spanner for $G$ that achieves a near-optimal bound of $O(n^{1/k}\mathrm{poly}(1/\epsilon ))$ on both sparsity and lightness. This algorithm can be implemented in the pointer-machine model within time $O(m\alpha (m,n)\mathrm{poly}(1/\epsilon )+SORT(m))$ and in the WORD RAM model within time $O(m\alpha (m,n)\mathrm{poly}(1/\epsilon ))$. The previous fastest constructions of $(2k-1)(1+\epsilon )$-spanners with near-optimal sparsity incur a runtime of is $O(\min \{m(n^{1+1/k})+n\log n,k{n}^{2+1/k}\})$, even regardless of the lightness. Importantly, the greedy spanner for stretch $2k-1$ has sparsity $O(n^{1/k})$ -- with no $\epsilon$-dependence whatsoever, but its runtime is $O(m(n^{1+1/k}+n\log n))$. Moreover, the state-of-the-art lightness bound of any $(2k-1)$-spanner is poor, even regardless of the sparsity and runtime.

37 pages, 5 figures