(1+epsilon, beta)-spanner constructions for general graphs

An (α,Β)-spanner of a graph G is a subgraph H such that d_H(u,w)\le α\cdot d_G(u,w)+Β for every pair of vertices u,w, where d_{G'}(u,w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible (2κ-1,0)-spanner (a.k.a. multiplicative (2κ-1)-spanner) of size O(n^{1+1/κ}) for every integer κ\ge 1, and a polynomially constructible (1,2)-spanner (a.k.a. additive 2-spanner) of size \tO(n^{3/2}). This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant ε, δ > 0 there exists a constant Β = Β(ε, δ) such that for every n-vertex graph G there is an efficiently constructible (1+ ε, Β)-spanner of size O(n^{1 + δ}). It follows that for any constant ε, δ > 0 there exists a constant Β(ε, δ) such that for any n-vertex graph G = (V,E) there exists an efficiently constructible subgraph (V,H) with O(n^{1 +δ}) edges such that d_H(u,w) \le (1 + ε) d_G(u,w) for every pair of vertices.

Authors

• Michael Elkin
• David Peleg

Keywords

No keywords are indexed for this paper.