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

Let G = (V, E, w) be a weighted undirected graph on |V| = n vertices and |E| = m edges, let k ≥ 1 be any integer, and let ∊ < 1 be any parameter. We present the following results on fast constructions of spanners with near-optimal sparsity and lightness,1 which culminate a long line of work in this area. (By near-optimal we mean optimal under Erdos' girth conjecture and disregarding the ∊-dependencies.) There are (deterministic) algorithms for constructing (2k–1)(1 + ∊)-spanners for G with a near-optimal sparsity of O(n1/k · log(1/∊)/∊)). The first algorithm can be implemented in the pointer-machine model within time O(mα(m, n) · log(1/∊)/∊)+ SORT(m)), where α(·,·) 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/∊)/∊)). There is a (deterministic) algorithm for constructing a (2k–1)(1 + ∊)-spanner for G that achieves a near-optimal bound of O(n1/k ·poly(1/∊)) on both sparsity and lightness. This algorithm can be implemented in the pointer-machine model within time O(mα(m,n) · poly(1/∊) + SORT(m)) and in the Word RAM model within time O(mα(m,n) · poly(1/∊)). The previous fastest constructions of (2k–1)(1 + ∊)-spanners with near-optimal sparsity incur a runtime of is O(minm(n1+1/k) + n log n, k · n2+1/k), even regardless of the lightness. Importantly, the greedy spanner for stretch 2k–1 has sparsity O(n1/k) — with no ∊-dependence whatsoever, but its runtime is O(m(n1+1/k + n log n)). Moreover, the state-of-the-art lightness bound of any (2k–1)-spanner (including the greedy spanner) is poor, even regardless of the sparsity and runtime.