(α, β)-Spanners and Hybrid Spanners with Nearly Tight Bounds

An (α, β)-spanner of an n-vertex undirected, unweighted graph G = (V, E) is a subgraph H satisfying, for all u, v ∈ V ,

For any k ∈ N, classical results show that a (2k -1, 0)-spanner with O(n 1+1/k ) edges exists and is asymptotically optimal under Erdős' girth conjecture. This conditional lower bound comes from adjacent pairs and does not rule out better stretch for more distant pairs. We present new spanner constructions that achieve nearly optimal guarantees for all distances d ≤ k. Specifically, we construct a spanner H ⊆ G with O(n 1+1/k +(k+d log d) n) edges, ensuring that any pair at original distance at most d satisfies dist H (u, v) ≤ 2k + O(d log d). Equivalently, the multiplicative stretch for pairs at distance d is 2k/d + O(log d).

In particular, setting d = k/ log k yields an (O(log k), O(k))-spanner with O(n 1+1/k + kn) edges. For comparison, Ben-Levy and Parter (SODA'20) obtained, for every fixed ε > 0 and sufficiently large k, an (O(k ε ), O ε (k))-spanner with O ε,k (n 1+1/k ) edges. Our result improves the multiplicative stretch from O(k ε ) to O(log k) while keeping the additive term linear in k, bringing us closer to the goal of (O(1), O(k))-spanners.

Furthermore, Ben-Levy and Parter obtained multiplicative stretch O ε (k/d) for distances d ≤ k 1-ε , for every fixed ε > 0, and an explicit bound of 7k/d for d ≤ √ k/2. We achieve 2k/d + O(log d), which is (2 + o(1))k/d whenever d = o(k/ log k).

Our second result is an improved construction of k-hybrid spanners, which guarantee stretch 2k -1 for adjacent pairs and k for non-adjacent pairs. Parter's original construction uses O(k 2 n 1+1/k ) edges; we achieve the same guarantees with O(n 1+1/k + kn) edges, removing the k 2 factor from the n 1+1/k term. For every fixed k, our edge bound is optimal up to a constant factor under Erdős' girth conjecture.