text: MPVX15 devised a distributed They actually showed a PRAM algorithm. The distributed algorithm with these properties is implicit in MPVX15 . algorithm in the CONGEST model, that given a parameter @math , constructs an @math -spanner of an input unweighted @math -vertex graph with @math expected edges in @math rounds of communication. In this paper we improve the result of MPVX15 , by showing a @math -round distributed algorithm in the same model, that constructs a @math -spanner with @math edges, with probability @math , for any @math . Moreover, when @math , our algorithm produces (still in @math rounds) ultra-sparse spanners, i.e., spanners of size @math , with probability @math . To our knowledge, this is the first distributed algorithm in the CONGEST or in the PRAM models that constructs spanners or skeletons (i.e., connected spanning subgraphs) that sparse. Our algorithm can also be implemented in linear time in the standard centralized model, and for large @math , it provides spanners that are sparser than any other spanner given by a known (near-)linear time algorithm. We also devise improved bounds (and algorithms realizing these bounds) for @math -spanners and emulators. In particular, we show that for any unweighted @math -vertex graph and any @math , there exists a @math -emulator with @math edges. All previous constructions of @math -spanners and emulators employ a superlinear number of edges, for all choices of parameters. Finally, we provide some applications of our results to approximate shortest paths' computation in unweighted graphs.
  @cite_35: A spanner of an undirected unweighted graph is a subgraph that approximates the distance metric of the original graph with some specified accuracy. Specifically, we say H ⊆ G is an f-spanner of G if any two vertices u,v at distance d in G are at distance at most f(d) in H. There is clearly some trade-off between the sparsity of H and the distortion function f, though the nature of the optimal trade-off is still poorly understood. In this article we present a simple, modular framework for constructing sparse spanners that is based on interchangable components called connection schemes. By assembling connection schemes in different ways we can recreate the additive 2- and 6-spanners of [1999] and [2009], and give spanners whose multiplicative distortion quickly tends toward 1. Our results rival the simplicity of all previous algorithms and provide substantial improvements (up to a doubly exponential reduction in edge density) over the comparable spanners of Elkin and Peleg [2004] and Thorup and Zwick [2006].
  @cite_3: An (α, β)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a (multiplicative) (2k−1, 0)-spanner of size O(n1+1 k) and an (additive) (1,2)-spanner of size O(n3 2). However no other additive spanners are known to exist. In this article we develop a couple of new techniques for constructing (α, β)-spanners. Our first result is an additive (1,6)-spanner of size O(n4 3). The construction algorithm can be understood as an economical agent that assigns costs and values to paths in the graph, purchasing affordable paths and ignoring expensive ones, which are intuitively well approximated by paths already purchased. We show that this path buying algorithm can be parameterized in different ways to yield other sparseness-distortion tradeoffs. Our second result addresses the problem of which (α, β)-spanners can be computed efficiently, ideally in linear time. We show that, for any k, a (k,k−1)-spanner with size O(kn1+1 k) can be found in linear time, and, further, that in a distributed network the algorithm terminates in a constant number of rounds. Previous spanner constructions with similar performance had roughly twice the multiplicative distortion.
  @cite_43: For an unweighted undirected graph G= (V,E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G'= (V,H), H ⊆ E, is called an (α,β)-spanner of G if for every pair of vertices u, v ∈ V, dist G' (u,v) ≤ α • dist G' (u,v) + β.It was shown in [20] that for any e > 0, κ = 1,2, ..., there exists an integer β = β(e,κ) such that for every n-vertex graph G there exists a (1+e,β)-spanner G' with O(n1+1 κ) edges. An efficient distributed protocol for constructing (1+e,β)-spanners was devised in [18]. The running time and the communication complexity of that protocol are O(n1+ρ) and O(|E|nρ), respectively, where ρ is an additional control parameter of the protocol that affects only the additive term β.In this paper we devise a protocol with a drastically improved running time (O(nρ) as opposed to (O(n1+ρ) for constructing (1+e,β)-spanners. Our protocol has the same communication complexity as the protocol of [18], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [18].We also show that our protocol for constructing (1+e, β)-spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and O(n1+1 κ • log n) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1 + e) and an additive term of β greater than the shortest paths. Our algorithm processes each edge in time O(nρ), for an arbitrarily small ρ > 0. The only previously known algorithm for the problem [21] constructs paths of length κ times greater than the shortest paths, has the same space requirements as our algorithm, but requires O(n1+1 κ) time for processing each edge of the input graph. However, the algorithm of [21] uses just one pass over the input, as opposed to the constant number of passes in our algorithm. We also show that any streaming algorithm for o(n)-approximate distance computation requires Ω(n) bits of space.
  @cite_8: A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a spanner and the quality of its approximation, so long as distance error is measured multiplicatively. A central open question in the field is to prove or disprove whether such a tradeoff exists also in the regime of additive error. That is, is it true that for all e>0, there is a constant ke such that every graph has a spanner on O(n1+e) edges that preserves its pairwise distances up to +ke? Previous lower bounds are consistent with a positive resolution to this question, while previous upper bounds exhibit the beginning of a tradeoff curve: all graphs have +2 spanners on O(n3 2) edges, +4 spanners on O(n7 5) edges, and +6 spanners on O(n4 3) edges. However, progress has mysteriously halted at the n4 3 bound, and despite significant effort from the community, the question has remained open for all 0 Our main result is a surprising negative resolution of the open question, even in a highly generalized setting. We show a new information theoretic incompressibility bound: there is no function that compresses graphs into O(n4 3 − e) bits so that distance information can be recovered within +no(1) error. As a special case of our theorem, we get a tight lower bound on the sparsity of additive spanners: the +6 spanner on O(n4 3) edges cannot be improved in the exponent, even if any subpolynomial amount of additive error is allowed. Our theorem implies new lower bounds for related objects as well; for example, the twenty-year-old +4 emulator on O(n4 3) edges also cannot be improved in the exponent unless the error allowance is polynomial. Central to our construction is a new type of graph product, which we call the Obstacle Product. Intuitively, it takes two graphs G,H and produces a new graph G H whose shortest paths structure looks locally like H but globally like G.
  @cite_21: 
  @cite_52: This paper considers additive and purely additive spanners. We present a new purely additive spanner of size O(n7 5) with additive stretch 4. This construction fills in the gap between the two existing constructions for purely additive spanners, one for 2-additive spanner of size O(n3 2) and the other for 6-additive spanner of size O(n4 3), and thus answers a main open question in this area. In addition, we present a construction for additive spanners with O(n1+δ) edges and additive stretch of O(n1 2−3δ 2) for any 3 17 ≤ δ < 1 3, improving the stretch of the existing constructions from O(n1−3δ) to O(√n1−3δ). Finally, we show that our (1,n1 2−3δ 2)-spanner construction can be tweaked to give a sublinear additive spanner of size O(n1+3 17) with additive stretch O(√distance).
  @cite_26: An additive spanner of an unweighted undirected graph G with distortion d is a subgraph H such that for any two vertices u, v G, we have _H ( u,v ) = _G ( u,v ) + d. For every k = O ( n n ), we construct a graph G on n vertices for which any additive spanner of G with distortion 2k - 1 has ( 1 k n^ 1 + 1 k ) edges. This matches the lower bound previously known only to hold under a 1963 conjecture of Erdos. We generalize our lower bound in a number of ways. First, we consider graph emulators introduced by Dor, Halperin, and Zwick (FOCS, 1996), where an emulator of an unweighted undirected graph G with distortion d is like an additive spanner except H may be an arbitrary weighted graph such that _G ( u,v ) _H ( u,v ) _G ( u,v ) + d. We show a lower bound of ( 1 k^2 n^ 1 + 1 k ) edges for distortion-(2k - 1) emulators. These are the first non-trivial bounds for k 3. Second, we parameterize our bounds in terms of the minimum degree of the graph. Namely, for minimum degree n^ 1 k+c for any c 0, we prove a bound of ( 1 k n^ 1 + 1 k - c(1 + 2 (k - 1)) ) for additive spanners and ( 1 k^2 n^ 1 + 1 k - c(1 + 2 (k - 1)) ) for emulators. For k = 2 these can be improved to ( n^ 3 2 - c ). This partially answers a question of (SODA, 2005) for additive spanners. Finally, we continue the study of pair-wise and source-wise distance preservers defined by Coppersmith and Elkin (SODA, 2005) by considering their approximate variants and their relaxation to emulators. We prove the first lower bounds for such graphs.
  @cite_7: In the recent past, there has been considerable progress in devising algorithms for the all-pairs shortest paths (APSP) problem running in time significantly smaller than the obvious time bound of O(n3). Unfortunately, all the new algorithms are based on fast matrix multiplication algorithms that are notoriously impractical. Our work is motivated by the goal of devising purely combinatorial algorithms that match these improved running times. Our results come close to achieving this goal, in that we present algorithms with a small additive error in the length of the paths obtained. Our algorithms are easy to implement, have the desired property of being combinatorial in nature, and the hidden constants in the running time bound are fairly small. Our main result is an algorithm which solves the APSP problem in unweighted, undirected graphs with an additive error of 2 in time @math . This algorithm returns actual paths and not just the distances. In addition, we give more efficient algorithms with running time @math for the case where we are only required to determine shortest paths between k specified pairs of vertices rather than all pairs of vertices. The starting point for all our results is an @math algorithm for distinguishing between graphs of diameter 2 and 4, and this is later extended to obtaining a ratio 2 3 approximation to the diameter in time @math . Unlike in the case of APSP, our results for approximate diameter computation can be extended to the case of directed graphs with arbitrary positive real weights on the edges.
  @cite_28: Shortest paths computations constitute one of the most fundamental network problems. Nonetheless, known parallel shortest-paths algorithms are generally inefficient: they perform significantly more work (product of time and processors) than their sequential counterparts. This gap, known in the literature as the “transitive closure bottleneck,” poses a long-standing open problem. Our main result is an O mn e 0 +s m+n1+ e 0 work polylog-time randomized algorithm that computes paths within (1 + O (1 polylog n ) of shortest from s source nodes to all other nodes in weighted undirected networks with n nodes and m edges (for any fixed e 0 >0). This work bound nearly matches the O d sm sequential time. In contrast, previous polylog-time algorithms required nearly min O d n3 , O d m2 work (even when s =1), and previous near-linear work algorithms required near- O ( n ) time. We also present faster sequential algorithms that provide good approximate distances only between “distant” vertices: We obtain an O m+sn n e 0 time algorithm that computes paths of weight (1+ O (1 polylog n ) dist + O ( w max polylog n ), where dist is the corresponding distance and w max is the maximum edge weight. Our chief instrument, which is of independent interest, are efficient constructions of sparse hop sets . A ( d ,e)-hop set of a network G =( V,E ) is a set E * of new weighted edges such that mimimum-weight d -edge paths in V,E∪E* have weight within (1+e) of the respective distances in G . We construct hop sets of size O n1+ e 0 where e= O (1 polylog n ) and d = O (polylog n ).
  @cite_6: An @math -spanner of a graph G is a subgraph H such that @math 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 @math -spanner (also known as multiplicative @math -spanner) of size @math for every integer @math , and a polynomially constructible (1,2)-spanner (also known as additive 2-spanner) of size @math . 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 @math there exists a constant @math such that for every @math -vertex graph G there is an efficiently constructible @math -spanner of size @math .
  @cite_27: We present a streaming algorithm for constructing sparse spanners and show that our algorithm significantly outperforms the state-of-the-art algorithm for this task (due to ). Specifically, the processing time per edge of our algorithm is O(1), and it is drastically smaller than that of the algorithm of , and all other efficiency parameters of our algorithm are no greater (and some of them are strictly smaller) than the respective parameters of the state-of-the-art algorithm. We also devise a fully dynamic centralized algorithm maintaining sparse spanners. This algorithm has incremental update time of O(1), and a nontrivial decremental update time. To our knowledge, this is the first fully dynamic centralized algorithm for maintaining sparse spanners that provides nontrivial bounds on both incremental and decremental update time for a wide range of stretch parameter t.
  @cite_50: We study the s-sources almost shortest paths(abbreviated s-ASP) problem. Given an unweightedgraph G e (V,E),and a subset S s Vof s nodes, the goal is to compute almostshortest paths between all the pairs of nodes St V. We devise an algorithm withrunning timeO(mEmnrp s mn1 p z)for this problem that computes the pathsPu,wfor all pairs (u,w) iS t V such that thelength ofPu,wis at most (1 p e)dG(u,w)p b(z,r,e), andb(z,r,e) is constant whenz, r, and e are arbitrarily smallconstants. We also devise a distributed protocol for thes-ASP problem that computes the pathsP u,w as above, and has time and communication complexities ofO(s mDiam(G) pn1 pz 2) (respectively,O(s mDiam(G) log3n p n1p z 2 log n)) andO(mEmnr ps m n1p z) (respectively,O(mEmnr ps m n1p z pn1 p r pz(r m z 2) 2)) in thesynchronous (respectively asynchronous) setting. Our sequential algorithm, as well as the distributed protocol,is based on a novel algorithm for constructing (1 pe, b(z,r, e))-spannersof size O(n1p z), developed in this article. Thisalgorithm has running time ofO(mEmnr), which issignificantly faster than the previously known algorithm given inElkin and Peleg [2001], whose running time isO(n2p r). We also develop the firstdistributed protocol for constructing (1 pe,b)-spanners. The communication complexity ofthis protocol is near optimal.
  @cite_16: A spanner is a sparse subgraph of a given graph that preserves approximate distance between each pair of vertices. In precise words, a t-spanner of a graph G = (V,E), for any t ∈ N, is a subgraph (V,ES), ES ⊆ E such that, for any u, v ∈ V , their distance in the subgraph is at most t times their distance in the original graph. The parameter t is called the stretch associated with the t-spanner. The concept of spanner was defined formally by Peleg and Schaffer [13] though the associated notion was used implicitly by Awerbuch [3] in the context of network synchronizers. Computing tspanner of smallest size for a given graph is a well motivated combinatorial problem with numerous applications in the area of distributed systems, communication networks and all pairs approximate shortest paths (see [4, 13] and references therein). However, computing t-spanner of smallest size for a graph is NP-hard. In fact, for t > 2, it is NP-hard [6] even to approximate the smallest size of t-spanner of a graph with ratio O(2(1−μ) lnn) for any μ > 0. Having realized this fact, researchers have pursued another direction : to design an efficient algorithm which, for a given graph on n vertices, outputs a t-spanner whose size is of the order of the maximum size of the sparsest tspanner of a graph on n vertices. A 43 years old girth lower bound conjecture by Erdős [7] implies that there are graphs on n vertices whose 2k as well as (2k− 1)spanner will requireΩ(n1+1 k) edges. This conjecture
  @cite_12: For an unweighted graph @math , @math is a subgraph if @math , and @math is a Steiner graph if @math , and for any pair of vertices @math , the distance between them in @math (denoted @math ) is at least the distance between them in @math (denoted @math ). In this paper we introduce the notion of distance preserver. A subgraph (resp., Steiner graph) @math of a graph @math is a subgraph (resp., Steiner) @math -preserver of @math if for every pair of vertices @math with @math , @math . We show that any graph (resp., digraph) has a subgraph @math -preserver with at most @math edges (resp., arcs), and there are graphs and digraphs for which any undirected Steiner @math -preserver contains @math edges. However, we show that if one allows a directed Steiner (diSteiner) @math -preserver, then these bounds can be improved. Specifically, we show that for any graph or digraph there exists a diSteiner @math -preserver with @math arcs, and that this result is tight up to a constant factor. We also study @math -preserving distance labeling schemes, that are labeling schemes that guarantee precise calculation of distances between pairs of vertices that are at a distance of at least @math one from another. We show that there exists a @math -preserving labeling scheme with labels of size @math , and that labels of size @math are required for any @math -preserving labeling scheme.
  @cite_61: Let G = (V,E) be an undirected weighted graph with vVv = n and vEv = m. Let k ≥ 1 be an integer. We show that G = (V,E) can be preprocessed in O(kmn1 k) expected time, constructing a data structure of size O(kn1p1 k), such that any subsequent distance query can be answered, approximately, in O(k) time. The approximate distance returned is of stretch at most 2k−1, that is, the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k−1. A 1963 girth conjecture of Erdos, implies that Ω(n1p1 k) space is needed in the worst case for any real stretch strictly smaller than 2kp1. The space requirement of our algorithm is, therefore, essentially optimal. The most impressive feature of our data structure is its constant query time, hence the name "oracle". Previously, data structures that used only O(n1p1 k) space had a query time of Ω(n1 k).Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs.
  @cite_9: We investigate the importance of space when solving problems based on graph distance in the streaming model. In this model, the input graph is presented as a stream of edges in an arbitrary order. The main computational restriction of the model is that we have limited space and therefore cannot store all the streamed data; we are forced to make space-efficient summaries of the data as we go along. For a graph of n vertices and m edges, we show that testing many graph properties, including connectivity (ergo any reasonable decision problem about distances) and bipartiteness, requires Ω(n) bits of space. Given this, we then investigate how the power of the model increases as we relax our space restriction. Our main result is an efficient randomized algorithm that constructs a (2t + 1)-spanner in one pass. With high probability, it uses O(t .n1+1 t log2n) bits of space and processes each edge in the stream in O(t2·n1 t log n) time. We find approximations to diameter and girth via the constructed spanner. For t = Ω(log n log log n), the space requirement of the algorithm is O(n .polylog n), and the per-edge processing time is O(polylog n). We also show a corresponding lower bound of t for the approximation ratio achievable when the space restriction is O(t.n1+1 t log2n).We then consider the scenario in which we are allowed multiple passes over the input stream. Here, we investigate whether allowing these extra passes will compensate for a given space restriction. We show that finding vertices at distance d from a particular vertex will always take d passes, for all d ∈ 1,...,t 2 , when the space restriction is o(n1+1 t). For girth, we show the existence of a direct trade-off between space and passes in the form of a lower bound on the product of the space requirement and number of passes. Finally, we conclude with two general techniques for speeding up the per-edge computation time of streaming algorithms while increasing the space by at most a log factor.
  @cite_1: We obtain new upper bounds on the additive distortion for graph emulators and spanners on relatively few edges. We introduce a new subroutine called "strip creation," and we combine this subroutine with several other ideas to obtain the following results: Every graph has a spanner on O(n1+e) edges with O(n 1 2 - e 2) additive distortion, for arbitrary e ∈ [0,1]. Every graph has an emulator on O(n1+e) edges with O(n 1 3 -- 2e 3) additive distortion whenever e ∈ [0, 1 5]. Every graph has a spanner on O(n1 + e) edges with O(n2 3 -- 5e 3) additive distortion whenever e ∈ [0, 1 4]. Our first spanner has the new best known asymptotic edge-error tradeoff for additive spanners whenever e ∈ [0, 1 7]. Our second spanner has the new best tradeoff whenever e ∈ [1 7, 3 17]. Our emulator has the new best asymptotic edge-error tradeoff whenever e ∈ [0, 1 5].
  @cite_24: We present efficient algorithms for computing very sparse low distortion spanners in distributed networks and prove some non-trivial lower bounds on the tradeoff between time, sparseness, and distortion. All of our algorithms assume a synchronized distributed network, where relatively short messages may be communicated in each time step. Our first result is a fast distributed algorithm for finding an ( O(2^ log ^ * n log n) ) -spanner with size O(n). Besides being nearly optimal in time and distortion, this algorithm appears to be the first that constructs an O(n)-size skeleton without requiring unbounded length messages or time proportional to the diameter of the network. Our second result is a new class of efficiently constructible (α, β)-spanners called Fibonacci spanners whose distortion improves with the distance being approximated. At their sparsest Fibonacci spanners can have nearly linear size, namely ( O(n( n)^ ) ) , where ( = (1 + 5 ) 2 ) is the golden ratio. As the distance increases the multiplicative distortion of a Fibonacci spanner passes through four discrete stages, moving from logarithmic to log-logarithmic, then into a period where it is constant, tending to 3, followed by another period tending to 1. On the lower bound side we prove that many recent sequential spanner constructions have no efficient counterparts in distributed networks, even if the desired distortion only needs to be achieved on the average or for a tiny fraction of the vertices. In particular, any distance preservers, purely additive spanners, or spanners with sublinear additive distortion must either be very dense, slow to construct, or have very weak guarantees on distortion.
  @cite_47: Let k ≥ 2 be an integer. We show that any undirected and unweighted graph G = (V, E) on n vertices has a subgraph G' = (V, E') with O(kn1+1 k) edges such that for any two vertices u, v ∈ V, if Δ G (u, v) = d, then Δ G' (u, v) = d+O(d1-1 k-1). Furthermore, we show that such subgraphs can be constructed in O(mn1 k) time, where m and n are the number of edges and vertices in the original graph. We also show that it is possible to construct a weighted graph G* = (V, E*) with O(kn1+1 (2k-1)) edges such that for every u, v ∈ V, if Δ G (u, v) = d, then Δ ≤ Δ G* (u, v) = d + O(d1-1 k-1). These are the first such results with additive error terms of the form o(d), i.e., additive error terms that are sublinear in the distance being approximated.
summary: Efficient algorithms for constructing @math -spanners were also devised in @cite_50 @cite_43 @cite_47 @cite_35 @cite_24 . These algorithms are based, however, on different approaches than that of the current paper. The latter is based on @cite_6 . Specifically, the approach of @cite_50 @cite_43 is based on @cite_21 @cite_28 construction of pairwise covers and hopsets, i.e., the algorithm works top-down. It recurses in small clusters, and eliminates large ones. The approach of @cite_47 @cite_35 @cite_24 is based on @cite_61 collection of trees, used originally for distance oracles. Streaming algorithms for constructing multiplicative spanners were given in @cite_9 @cite_27 @cite_16 , and near-additive spanners in @cite_50 @cite_43 . Spanners and emulators with sublinear error were given in @cite_47 @cite_35 . Spanners with purely additive error and lower bounds concerning them were given in @cite_7 @cite_6 @cite_12 @cite_3 @cite_52 @cite_26 @cite_1 @cite_8 .