(1 + ε,β)-Spanner Constructions for General Graphs

An { (α,β)-spanner} of a graph G is a subgraph H such that distH(u,w)≤ α· disttG(u,w)+β for every pair of vertices u,w, where distG'(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 (also known as multiplicative (2κ-1)-spanner) of size O(n1+1/κ) for every integer κ≥ 1, and a polynomially constructible (1,2)-spanner (also known as additive 2-spanner) of size O(n3/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(n1 + λ).