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.
There are several algorithms for computing multiplicative and additive spanners in weighted and unweighted graphs. In unweighted graphs, for any integer @math , Halperin and Zwick @cite_1 gave a linear time algorithm to compute a multiplicative @math -spanner of size @math , where @math is the number of vertices. Note that for @math one obtains a spanner with multiplicative stretch @math and with size @math : we will use this type of spanner in Theorem . Analogous results are also known for weighted graphs @cite_10 @cite_18 @cite_13 .
@cite_13 @cite_10 @cite_18 @cite_1
2099237198 2809995963 2042333226 1574233320 2061507472 2951859740 2156047991 2963530558 2774521735 1972920042 1564010364 2122632420 1607700260 2562627112 2032654248 2227069303 2033607935 1518503263 2092938419 2508647357
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). 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 . 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. 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]. 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. Let G=(V,E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most 1 is as hard as Boolean matrix multiplication. Building on recent work of [SIAM J. Comput., 28 (1999), pp. 1167--1181], we describe an @math -time algorithm APASP2 for computing all distances in G with an additive one-sided error of at most 2. Algorithm APASP2 is simple, easy to implement, and faster than the fastest known matrix-multiplication algorithm. Furthermore, for every even k>2, we describe an @math -time algorithm APASPk for computing all distances in G with an additive one-sided error of at most k. We also give an @math -time algorithm @math for producing stretch 3 estimated distances in an unweighted and undirected graph on n vertices. No constant stretch factor was previously achieved in @math time. We say that a weighted graph F=(V,E') k-emulates an unweighted graph G=(V,E) if for every @math we have @math . We show that every unweighted graph on n vertices has a 2-emulator with @math edges and a 4-emulator with @math edges. These results are asymptotically tight. Finally, we show that any weighted undirected graph on n vertices has a 3-spanner with @math edges and that such a 3-spanner can be built in @math time. We also describe an @math -time algorithm for estimating all distances in a weighted undirected graph on n vertices with a stretch factor of at most 3. [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. We show that the greedy spanner algorithm constructs a @math -spanner of weight @math for a point set in metrics of doubling dimension @math , resolving an open problem posed by Gottlieb. Our result generalizes the result by Narasimhan and Smid who showed that a point set in @math -dimension Euclidean space has a @math -spanner of weight at most @math . Our proof only uses the packing property of doubling metrics and thus implies a much simpler proof for the same result in Euclidean space. 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. Thorup and Zwick showed that for any integer k≥ 1, it is possible to preprocess any positively weighted undirected graph G=(V,E), with |E|=m and |V|=n, in O(kmn @math ) expected time and construct a data structure (a (2k–1)-approximate distance oracle) of size O(kn @math ) capable of returning in O(k) time an approximation @math of the distance δ(u,v) from u to v in G that satisfies @math , for any two vertices u,v∈ V. They also presented a much slower O(kmn) time deterministic algorithm for constructing approximate distance oracle with the slightly larger size of O(kn @math log n). We present here a deterministic O(kmn @math ) time algorithm for constructing oracles of size O(kn @math ). Our deterministic algorithm is slower than the randomized one by only a logarithmic factor. Using our derandomization technique we also obtain the first deterministic linear time algorithm for constructing optimal spanners of weighted graphs. We do that by derandomizing the O(km) expected time algorithm of Baswana and Sen (ICALP’03) for constructing (2k–1)-spanners of size O(kn @math ) of weighted undirected graphs without incurring any asymptotic loss in the running time or in the size of the spanners produced. 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. 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. Let G=(V,E) be an undirected unweighted graph on n vertices. A subgraph H of G is called an (all-pairs) purely additive spanner with stretch β if for every (u,v)∈V×V, d i s t H (u,v)≤d i s t G (u,v) + β. The problem of computing sparse spanners with small stretch β is well-studied. Here we consider the following variant: we are given ( P V V ) and we seek a sparse subgraph H where d i s t H (u,v)≤d i s t G (u,v) + β for each ((u,v) P ). That is, distances for pairs outside ( P ) need not be well-approximated in H. Such a subgraph is called a pairwise spanner with additive stretch β and our goal is to construct such subgraphs that are sparser than all-pairs spanners with the same stretch. We show sparse pairwise spanners with additive stretch 4 and with additive stretch 6. We also consider the following special cases: ( P = S V ) and ( P = S T ), where S⊆V and T⊆V, and show sparser pairwise spanners for these cases. We present efficient algorithms for computing very sparse low distortion spanners in distributed networks and prove some non-trivial lower bounds on the trade-off 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 an O(log n)1+o(1)-time algorithm for finding a (2O(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 a 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 O(n(log log n)φ) where φ = 1+☂5 2 is the golden ratio. As the distance increases the Fibonacci spanner's multiplicative distortion passes through four discrete stages, moving from logarithmic to doubly 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. 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. 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. Given as input an edge-weighted graph, we analyze two algorithms for finding subgraphs with low total edge weight. The first algorithm finds a separator subgraph with a small number of components, and is analyzed for graphs with an arbitrary excluded minor. The second algorithm finds a spanner with small stretch factor, and is analyzed for graphs in a hereditary family G(k). These results imply (i) a QPTAS (quasi-polynomial time approximation scheme) for the TSP (traveling salesperson problem) in unweighted graphs with an excluded minor, and (ii) a QPTAS for the TSP in weighted graphs with bounded genus. 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. Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say O(n1+Δ) bits. There is an inherent tradeoff between the sparsity parameter Δ and the stretch function f of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem. It has been known for some time that when Δ ≥ 1 3 there are schemes with constant additive stretch (distance d is stretched to at most f(d) = d + O(1)), and recent results of Abboud and Bodwin show that when Δ In this paper we show that the lower bound of Abboud and Bodwin is just the first step in a hierarchy of lower bounds that characterize the asymptotic behavior of the optimal stretch function f for sparsity parameter Δ ∈ (0,1 3). Specifically, for any integer k ≥ 2, any compression scheme with size [EQUATION] has a sublinear additive stretch function f: f(d) = d + Ω(d1−1 k). This lower bound matches Thorup and Zwick's (2006) construction of sublinear additive emulators. It also shows that Elkin and Peleg's (1 + ϵ, β)-spanners have an essentially optimal tradeoff between Δ, ϵ, and β, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal. To complement these lower bounds we present a new construction of (1 + ϵ, O(k ϵ)k−1)-spanners with size [EQUATION], where hk Our lower bound technique exhibits several interesting degrees of freedom in the framework of Abboud and Bodwin. By carefully exploiting these freedoms, we are able to obtain lower bounds for several related combinatorial objects. We get lower bounds on the size of (β, ϵ)-hopsets, matching Elkin and Neiman's construction (2016), and lower bounds on shortcutting sets for digraphs that preserve the transitive closure. Our lower bound simplifies Hesse's (2003) refutation of Thorup's conjecture (1992), which stated that adding a linear number of shortcuts suffices to reduce the diameter to polylogarithmic. Finally, we show matching upper and lower bounds for graph compression schemes that work for graph metrics with girth at least 2γ + 1. One consequence is that 's (2010) additive O(γ)-spanners with size [EQUATION] cannot be improved in the exponent.