View/hide extracted text (may have errors)
New Additive Spanners Shiri Chechik * Abstract and 5 [29]. This paper considers additive and purely additive span- Although many papers considered additive span- ners. We present a new purely additive spanner of size ners or mixed spanners, several key questions in this ˜(n7/5) with additive stretch 4. This construction fills area remain open. The girth conjecture applies only in the gap between the two existing constructions for to short distances. In particular, it does not contradict purely additive spanners, one for 2-additive spanner of the existence of (1, 2k−2)-spanners of size O(n1+1/k), or size O(n3/2) and the other for 6-additive spanner of size any (α,β)-spanners of size O(n1+1/k) such that α+β = O(n4/3), and thus answers a main open question in this 2k − 1 with α > 1 and β > 0. The first construction for area. In addition, we present a construction for addi- purely additive spanners was presented by Aingworth et tive spanners with ˜(n1+δ) edges and additive stretch al. [1]. They show how to efficiently construct a (1, 2) of ˜(n1/2−3δ/2) for any 3/17 6 δ < 1/3, improving the spanner, or a 2-additive spanner for short, with O(n3/2) stretch of the existing constructions from O(n1−3δ) to edges (see [11, 15, 28, 24] for further follow-up). Later,√ ˜( n1−3δ). Finally, we show that our (1,n1/2−3δ/2)- an efficient construction for 6-additive spanners with spanner construction can be tweaked to give a sublin- O(n4/3) edges was presented by Baswana et al. [4, 5]. stretch O( distance). 6-additive spanners with ˜(n4/3) edges with better con-√) with additiveWoodruff [31] later presented a different construction for17/1+3n(˜ear additive spanner of size struction time. These are the only two purely additive 1 Introduction spanners known so far. A major open problem in this field concerns the existence of purely additive spanners Graph spanners are sparse subgraphs that faithfully pre- 1+δ) edges for any fixed δ > 0. Woodruff [30]n(Owith serve the pairwise distances of a given graph. Formally, showed a lower bound for additive spanners matching an (α,β)-spanner of a graph G = (V,E) is a subgraph the girth conjecture bounds but independent of the cor- H such that for any pair of nodes s,t, dist(s,t,H) 6 rectness of the conjecture. More precisely, he showed α · dist(s,t,G)+ β, where dist(s,t,H′) for a subgraph the existence of graphs for which any spanner of size H′ is the distance from s to t in H′. If α = 1 we say O(k−1n1+1/k) has an additive stretch of at least 2k − 1. that the spanner is additive and if in addition β = O(1), In the absence of additional purely additive span- we say that the spanner is purely additive. If β = 0 we ners or impossibility results, attempts were made to seek say that the spanner is multiplicative, otherwise we say spanners with either non-constant additive stretch or a that the spanner is mixed. mix of both multiplicative and additive stretch (see, e.g., Graph spanners were extensively studied since they [15, 28, 23, 5]). were first introduced in [19, 20] in the late 80’s. Bollob´as et al. [6] presented efficient constructions Many distributed applications use spanners as a key for a spectrum of additive spanners with additive ingredient, e.g., synchronizers [20], compact routing stretch that depends on n. More precisely, they show schemes [21, 9, 26, 10, 25], distance oracles [3, 27], 1−2δ)-spanner with,nhow to efficiently construct a (1 broadcasting [18], near-shortest path algorithms [12, 13, 1/δn1+δ) edges for any δ > 0. This additive stretch(2O 16], etc. 1−3δ) by Baswana et al. in,nwas later improved to (1 Much of the work on spanners considers multiplica- 9/16−7δ/8) by Pettie [22, 23] (the lat-,n[4, 5] and to (1 tive spanners. It is well-known that one can efficiently ter is smaller than the former for every δ < 7/34). In construct a (2k−1, 0)-spanner with O(n1+1/k) edges [2]. addition, sublinear additive spanners, namely, additive This size-stretch ratio is conjectured to be tight based spanners with stretch that is sublinear in the distances, on the girth conjecture of Erd˝os [17]. The girth conjec- were also considered. Thorup and Zwick [28] showed ture has been proved for the specific cases of k = 1, 2, 3, 1+1/k) such thatkn(Ohow to construct a spanner of size for every pair of nodes s and t, the additive stretch is O(d1−1/k + 2k), where d = dist(s,t). Pettie [22, 23] *Microsoft Research Silicon Valley, Mountain View CA, USA. Email: schechik@microsoft.com. later improved that result presenting an efficient span- 498 Copyright © SIAM. Unauthorized reproduction of this article is prohibited.
