Given an undirected @math -node unweighted graph @math , a spanner with stretch function @math is a subgraph @math such that, if two nodes are at distance @math in @math , then they are at distance at most @math in @math . Spanners are very well studied in the literature. The typical goal is to construct the sparsest possible spanner for a given stretch function. In this paper we study pairwise spanners, where we require to approximate the @math - @math distance only for pairs @math in a given set @math . Such @math -spanners were studied before [Coppersmith,Elkin'05] only in the special case that @math is the identity function, i.e. distances between relevant pairs must be preserved exactly (a.k.a. pairwise preservers). Here we present pairwise spanners which are at the same time sparser than the best known preservers (on the same @math ) and of the best known spanners (with the same @math ). In more detail, for arbitrary @math , we show that there exists a @math -spanner of size @math with @math . Alternatively, for any @math , there exists a @math -spanner of size @math with @math . We also consider the relevant special case that there is a critical set of nodes @math , and we wish to approximate either the distances within nodes in @math or from nodes in @math to any other node. We show that there exists an @math -spanner of size @math with @math , and an @math -spanner of size @math with @math . All the mentioned pairwise spanners can be constructed in polynomial time.
Graph spanners were introduced by Peleg and Schaffer @cite_0 in 1989. Spanners have been extensively studied since then, and there are numerous applications involving spanners, such as algorithms for approximate shortest paths @cite_3 @cite_12 @cite_16 , labeling schemes @cite_6 @cite_17 , approximate distance oracles @cite_21 @cite_11 @cite_20 , routing @cite_14 @cite_5 @cite_4 , and network design @cite_8 .
@cite_11 @cite_14 @cite_4 @cite_8 @cite_21 @cite_3 @cite_6 @cite_0 @cite_5 @cite_16 @cite_20 @cite_12 @cite_17
2061507472 1966206200 2099237198 2809995963 1574233320 2092938419 1489900072 2227069303 2154201790 2951859740 1525064252 1505970908 2963530558 2042333226 2002041206 1986144992 2122632420 1997369416 1607700260 2902989566
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]. 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 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. An (α,β)-spanner of an n-vertex graph G = (V,E) is a subgraph H of G satisfying that dist(u, v, H) ≤ α·dist(u, v, G) + β for every pair (u, v) ∈ V ×V, where dist(u,v,G′) denotes the distance between u and v in G′ ⊆ G. It is known that for every integer k ≥ 1, every graph G has a polynomially constructible (2k − 1,0)-spanner of size O(n 1 + 1 k ). This size-stretch bound is essentially optimal by the girth conjecture. Yet, it is important to note that any argument based on the girth only applies to adjacent vertices. It is therefore intriguing to ask if one can “bypass” the conjecture by settling for a multiplicative stretch of 2k − 1 only for neighboring vertex pairs, while maintaining a strictly better multiplicative stretch for the rest of the pairs. We answer this question in the affirmative and introduce the notion of k-hybrid spanners, in which non neighboring vertex pairs enjoy a multiplicative k stretch and the neighboring vertex pairs enjoy a multiplicative (2k − 1) stretch (hence, tight by the conjecture). We show that for every unweighted n-vertex graph G, there is a (polynomially constructible) k-hybrid spanner with O(k 2 ·n 1 + 1 k ) edges. This should be compared against the current best (α,β) spanner construction of [5] that obtains (k,k − 1) stretch with O(k ·n 1 + 1 k ) edges. An alternative natural approach to bypass the girth conjecture is to allow ourself to take care only of a subset of pairs S ×V for a given subset of vertices S ⊆ V referred to here as sources. Spanners in which the distances in S ×V are bounded are referred to as sourcewise spanners. Several constructions for this variant are provided (e.g., multiplicative sourcewise spanners, additive sourcewise spanners and more). Let G(V, E) be an undirected weighted graph with |V| = n, and |E| = m. A t-spanner of the graph G(V, E) is a sub-graph G(V, ES) such that the distance between any pair of vertices in the spanner is at most t times the distance between the two in the given graph. A 1963 girth conjecture of Erdos implies that Ω(n1+1 k) edges are required in the worst case for any (2k - 1)-spanner, which has been proved for k = 1, 2, 3, 5. There exist polynomial time algorithms that can construct spanners with the size that matches this conjectured lower bound, and the best known algorithm takes O(mn1 k) expected running time. In this paper, we present an extremely simple linear time randomized algorithm that constructs (2k - 1)-spanner of size matching the conjectured lower bound. Our algorithm requires local information for computing a spanner, and thus can be adapted suitably to obtain efficient distributed and parallel algorithms. Let G = (V,E) be an undirected weighted graph on |V | = n vertices and |E| = m edges. A t-spanner of the graph G, for any t ≥ 1, is a subgraph (V,ES), ES ⊆ E, such that the distance between any pair of vertices in the subgraph is at most t times the distance between them in the graph G. Computing a t-spanner of minimum size (number of edges) has been a widely studied and well-motivated problem in computer science. In this paper we present the first linear time randomized algorithm that computes a t-spanner of a given weighted graph. Moreover, the size of the t-spanner computed essentially matches the worst case lower bound implied by a 43-year old girth lower bound conjecture made independently by Erdos, Bollobas, and Bondy & Simonovits. Our algorithm uses a novel clustering approach that avoids any distance computation altogether. This feature is somewhat surprising since all the previously existing algorithms employ computation of some sort of local or global distance information, which involves growing either breadth first search trees up to t(t)-levels or full shortest path trees on a large fraction of vertices. The truly local approach of our algorithm also leads to equally simple and efficient algorithms for computing spanners in other important computational environments like distributed, parallel, and external memory. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007 Preliminary version of this work appeared in the 30th International Colloquium on Automata, Languages and Programming, pages 384–396, 2003. Given a graph G, a subgraph G′ is a t-spanner of G, if for every u, v ∈ V, the distance from u to v in G′ is at most t times longer than the distance in G. In this paper we give a very simple algorithm for constructing sparse spanners for arbitrary weighted graphs. We then apply this algorithm to obtain specific results for planar graphs and Euclidean graphs. We discuss the optimality of our results and present several nearly matching lower bounds. 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. Given a metric M = (V, d), a graph G = (V, E) is a t-spanner for M if every pair of nodes in V has a "short" path (i.e., of length at most t times their actual distance) between them in the spanner. Furthermore, this spanner has a hop diameter bounded by D if every such short path also uses at most D edges. We consider the problem of constructing sparse (1 + e)-spanners with small hop diameter for metrics of low doubling dimension.In this paper, we show that given any metric with constant doubling dimension k, and any 0 < e < 1, one can find a (1 + e)-spanner for the metric with nearly linear number of edges (i.e., only O(n log* n + ne-O(k)) edges) and a constant hop diameter, and also a (1 + e)-spanner with linear number of edges (i.e., only ne-O(k) edges) which achieves a hop diameter that grows like the functional inverse of the Ackermann's function. Moreover, we prove that such tradeoffs between the number of edges and the hop diameter are asymptotically optimal. Given an undirected @math -node unweighted graph @math , a spanner with stretch function @math is a subgraph @math such that, if two nodes are at distance @math in @math , then they are at distance at most @math in @math . Spanners are very well studied in the literature. The typical goal is to construct the sparsest possible spanner for a given stretch function. In this paper we study pairwise spanners, where we require to approximate the @math - @math distance only for pairs @math in a given set @math . Such @math -spanners were studied before [Coppersmith,Elkin'05] only in the special case that @math is the identity function, i.e. distances between relevant pairs must be preserved exactly (a.k.a. pairwise preservers). Here we present pairwise spanners which are at the same time sparser than the best known preservers (on the same @math ) and of the best known spanners (with the same @math ). In more detail, for arbitrary @math , we show that there exists a @math -spanner of size @math with @math . Alternatively, for any @math , there exists a @math -spanner of size @math with @math . We also consider the relevant special case that there is a critical set of nodes @math , and we wish to approximate either the distances within nodes in @math or from nodes in @math to any other node. We show that there exists an @math -spanner of size @math with @math , and an @math -spanner of size @math with @math . All the mentioned pairwise spanners can be constructed in polynomial time. Spanners are sparse subgraphs that preserve distances up to a given factor in the underlying graph. Recently spanners have found important practical applications in metric space searching and message distribution in networks. These applications use some variant of the so-called greedy algorithm for constructing the spanner — an algorithm that mimics Kruskal’s minimum spanning tree algorithm. Greedy spanners have nice theoretical properties, but their practical performance with respect to total weight is unknown. In this paper we give an exact algorithm for constructing minimum-weight spanners in arbitrary graphs. By using the solutions (and lower bounds) from this algorithm, we experimentally evaluate the performance of the greedy algorithm for a set of realistic problem instances. Part I. Introduction: 1. Introduction 2. Algorithms and graphs 3. The algebraic computation-tree model Part II. Spanners Based on Simplical Cones: 4. Spanners based on the Q-graph 5. Cones in higher dimensional space and Q-graphs 6. Geometric analysis: the gap property 7. The gap-greedy algorithm 8. Enumerating distances using spanners of bounded degree Part III. The Well Separated Pair Decomposition and its Applications: 9. The well-separated pair decomposition 10. Applications of well-separated pairs 11. The Dumbbell theorem 12. Shortcutting trees and spanners with low spanner diameter 13. Approximating the stretch factor of Euclidean graphs Part IV. The Path Greedy Algorithm: 14. Geometric analysis: the leapfrog property 15. The path-greedy algorithm Part V. Further Results and Applications: 16. The distance range hierarchy 17. Approximating shortest paths in spanners 18. Fault-tolerant spanners 19. Designing approximation algorithms with spanners 20. Further results and open problems. [43] devised a distributed1 algorithm in the CONGEST model, that given a parameter k = 1, 2, ..., constructs an O(k)-spanner of an input unweighted n-vertex graph with O(n1+1 k) expected edges in O(k) rounds of communication. In this paper we improve the result of [43], by showing a k-round distributed algorithm in the same model, that constructs a (2k − 1)-spanner with O(n1+1 k ϵ) edges, with probability 1 − ϵ, for any ϵ > 0. Moreover, when k = ω(log n), our algorithm produces (still in k rounds) ultra-sparse spanners, i.e., spanners of size n(1 + o(1)), with probability 1 − o(1). 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 k, 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 (1 + ϵ, β)-spanners and emulators. In particular, we show that for any unweighted n-vertex graph and any ϵ > 0, there exists a [EQUATION]-emulator with O(n) edges. All previous constructions of (1 + ϵ, β)-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. 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 . Given a graphG, a subgraphG' is at-spanner ofG if, for everyu,v ?V, the distance fromu tov inG' is at mostt times longer than the distance inG. In this paper we give a simple algorithm for constructing sparse spanners for arbitrary weighted graphs. We then apply this algorithm to obtain specific results for planar graphs and Euclidean graphs. We discuss the optimality of our results and present several nearly matching lower bounds. We present an O(nlogn)-approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, given a graph G=(V,E) with nonnegative edge lengths d:E->R^>=^0 and a stretchk>=1, a subgraph H=(V,E"H) is a k-spanner of G if for every edge (s,t)@?E, the graph H contains a path from s to t of length at most [email protected]?d(s,t). The previous best approximation ratio was [email protected]?(n^2^ ^3), due to Dinitz and Krauthgamer (STOC @?11). We also improve the approximation ratio for the important special case of directed 3-spanners with unit edge lengths from [email protected]?(n) to O(n^1^ ^3logn). The best previously known algorithms for this problem are due to Berman, Raskhodnikova and Ruan (FSTTCS @?10) and Dinitz and Krauthgamer. The approximation ratio of our algorithm almost matches Dinitz and [email protected]?s lower bound for the integrality gap of a natural linear programming relaxation. Our algorithm directly implies an O(n^1^ ^3logn)-approximation for the 3-spanner problem on undirected graphs with unit lengths. An easy O(n)-approximation algorithm for this problem has been the best known for decades. Finally, we consider the Directed Steiner Forest problem: given a directed graph with edge costs and a collection of ordered vertex pairs, find a minimum-cost subgraph that contains a path between every prescribed pair. We obtain an approximation ratio of O(n^2^ ^3^+^@e) for any constant @e>0, which improves the O(n^@[email protected]?min(n^4^ ^5,m^2^ ^3)) ratio due to Feldman, Kortsarz and Nutov ([email protected]?12). 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. A k -spanner of a connected graph G=(V,E) is a subgraph G' consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G' is larger than the distance in G by no more than a factor of k . This paper concerns the hardness of finding spanners with a number of edges close to the optimum. It is proved that for every fixed k , approximating the spanner problem is at least as hard as approximating the set-cover problem. We consider the problem of efficiently finding an additive C-spanner of an undirected unweighted graph G, that is, a subgraph H so that for all pairs of vertices u,v, δ H (u,v) ≤ δ G (u,v) + C, where δ denotes shortest path distance. It is known that for every graph G, one can find an additive 6-spanner with O(n 4 3) edges in O(mn 2 3) time. It is unknown if there exists a constant C and an additive C-spanner with o(n 4 3) edges. Moreover, for C ≤ 5 all known constructions require Ω(n 3 2) edges. Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say @math bits. There ...