Almost Shortest Paths with Near-Additive Error in Weighted Graphs
Michael Elkin Yuval Gitlitz Ofer Neiman
cs.DS


1]Michael Elkin
1]Yuval Gitlitz
1]Ofer Neiman

[1]Department of Computer Science, Ben-Gurion University of the Negev,
	Beer-Sheva, Israel. Email: , 


Exploiting the Redundancy in Convolutional Filters for Parameter Reduction 

    [
     ^⋆  Laboratoire d'Informatique et des Systèmes, Université de Toulon, Aix Marseille Univ, CNRS UMR 7020, LIS, Marseille, France

boizot@univ-tln.fr; 

^†  Department of Mathematics, Lehigh University, Bethlehem, PA, USA. 

lus219@lehigh.edu; 

 

This research has been partially supported by the ANR SRGI (reference ANR-15-CE40-0018). 


This is a post-peer-review, pre-copyedit version of an article published in Journal of Mathematical Imaging and Vision (JIMIV). The final authenticated version is available online at: <http://dx.doi.org/10.1007/s10851-020-00990-5>

   
      
   

 
 

====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================


Let G=(V,E,w) be a weighted undirected graph with n vertices and m edges, and fix a set of s sources S⊆ V. We study the problem of computing almost shortest paths (ASP) for all pairs in S × V in both classical centralized and parallel (PRAM) models of computation. Consider the regime of multiplicative approximation of 1+, for an arbitrarily small constant > 0 (henceforth (1+)-ASP for S × V). In this regime existing centralized algorithms require 
Ω(min{|E|s,n^ω}) time, where ω < 2.372 is the matrix multiplication exponent. Existing PRAM algorithms with polylogarithmic depth (aka time) require work Ω(min{|E|s,n^ω}).

In a bold attempt to achieve centralized time close to the lower bound  of m + n s, Cohen <cit.> devised an algorithm which, in addition to the multiplicative stretch of 1+, allows also additive error of β· W_max, where 
W_max is the maximum edge weight in G (assuming that the minimum edge weight is 1), and β = (log n)^O(log 1/ρ/ρ) is polylogarithmic in n. It also depends on the (possibly) arbitrarily small parameter ρ >0 that determines the running time O((m + ns)n^ρ) of the algorithm.

The tradeoff of <cit.> was improved in <cit.>, whose algorithm has similar approximation guarantee and running time, but its β is (1/ρ)^O(log 1/ρ/ρ). However, the latter algorithm produces distance estimates rather than actual approximate shortest paths.
Also, the additive terms in <cit.> depend linearly on a possibly quite large global maximum edge weight W_max. 

In the current paper we significantly improve this state of affairs. Our centralized algorithm has running time O((m+ ns)n^ρ), and its PRAM counterpart has polylogarithmic depth and work O((m + ns)n^ρ), for an arbitrarily small constant ρ > 0. 
For  a pair (s,v) ∈ S× V, it provides a path of length d̂(s,v) that satisfies 
d̂(s,v) ≤ (1+)d_G(s,v) + β· W(s,v), where W(s,v) is the weight of the heaviest edge on some shortest s-v path. Hence our additive term depends linearly on a local maximum edge weight, as opposed to the global maximum edge weight in <cit.>. Finally, our β = (1/ρ)^O(1/ρ), i.e., it is significantly smaller than in <cit.>.

We also extend a centralized algorithm of Dor et al. <cit.>. For a parameter κ = 1,2,…, this algorithm provides for unweighted graphs a purely additive approximation of 2(κ -1) for all pairs shortest paths (APASP) in time (n^2+1/κ).
Within the same running time, our algorithm for weighted graphs provides a purely additive error of 2(κ - 1) W(u,v), for every vertex pair (u,v) ∈V  2, with W(u,v) defined as above.

On the way to these results we devise a suite of novel constructions of spanners, emulators and hopsets.

empty



§ INTRODUCTION




We study the problem of computing almost shortest paths from a set S ⊆ V of designated vertices, called sources, to all other vertices in an n-vertex m-edge weighted undirected graph G = (V,E,w), with non-negative edge weights. 
We aim at approximation guarantee of the form (1+ ,β· W), meaning that for every pair (s,v) ∈ S × V, our algorithm will return a path of length d̂(s,v) (called distance estimate) that satisfies

    d_G(s,v) ≤d̂(s,v) ≤ (1+ ) d_G(s,v) + β· W(s,v) ,

where W(s,v) is the weight of the heaviest edge on some shortest s-v path in G (If there are multiple shortest paths, pick the one with minimal W(s, v)). 

Here > 0 is an arbitrarily small positive constant, and β is typically a large constant that depends on , and on the running time of the algorithm.[In the introduction we will mostly suppress the dependence on . It can however be found in the technical part of the paper.]
We call this problem (1 + ,β· W)-ASP for S × V. 

The problem of computing approximate shortest paths is one of the most central, fundamental and well-researched problems in Graph Algorithms. We study this problem in both the classical centralized and in the parallel (PRAM CRCW) models of computation.
Next, we overview the main previous results for this problem in these two settings, and describe our new results.
We start with the centralized model, and then turn our attention to the PRAM model.




 §.§ Centralized Setting




The classical algorithm of Dijkstra for the exact single-source shortest path (SSSP) problem provides running time of O(m + n log n) <cit.>. Thorup <cit.> devised an algorithm with running time O(m + nloglog n) for the case when all edge weights are integer. Using this algorithm separately from each of the s = |S| sources results in running time of at least (m · s). 

On the opposite end of the spectrum, one can compute (1+)-APASP (All Pair Approximate Shortest Paths) using matrix multiplication in (n^ω) time <cit.>, where ω < 2.372 is the matrix multiplication exponent <cit.>. 
There are also a number of combinatorial (i.e., not exploiting fast matrix multiplication) APASP algorithms. 
In particular, Cohen and Zwick <cit.> showed that 3-APASP can be computed in (n^2) time. (They also provided a few additional algorithms with approximation ratio between 2 and 3 and running time greater than n^2.)
Baswana and Kavitha <cit.> improved their approximation guarantee to (2,W) (with the same running time of (n^2)),
and
with W defined as in (<ref>). 

Finally, Cohen <cit.> devised an algorithm that for an arbitrarily small parameter ρ > 0, solves (1+,β· W_max)-ASP for S × V in ((m + s· n) · n^ρ) time[The running time of the algorithm of <cit.>, as well as of the algorithm of <cit.> and of our algorithm, is actually slightly better than O((m+sn)n^ρ). Specifically, it is roughly O(m n^ρ + s n^1+1/2^1/ρ). We use the simpler expression of O((m + sn)n^ρ) to simplify presentation. More precise and general bounds can be found in the technical part of the paper.], with 
β = β_Coh = (log n)^O(log (1/ρ)ρ). Here W_max is the maximum edge weight in the entire graph (assuming the minimum edge weight is 1). 


This result was improved by Elkin <cit.>. The algorithm of Elkin <cit.> also solves (1+,β· W_max)-ASP for S × V in ((m + sn)n^ρ) time, with β = β_Elk = (1/ρ)^O(log(1/ρ)/ρ). 

This algorithm 

 reports distance estimates, rather than actual paths.[There is a variant of the algorithm of <cit.> which reports actual paths, but requires time ((m + sn)n^ρ· W_max). This running time is  typically prohibitively large as it depends linearly on W_max.] 

The running time of <cit.> is close (up to n^ρ, for an arbitrarily small constant ρ >0) to the lower bound of Ω(m + n· s). This is unlike other aforementioned algorithms, whose running time is much larger, i.e., 
Ω(min{m · s,n^2}). However, the algorithms of <cit.> suffer from a number of drawbacks.
First, their additive term is linear in the maximum edge weight  W_max. Second, the coefficient β in them is quite large, even for a relatively large values of the parameter ρ. Third, as was mentioned above, 

the algorithm of <cit.>
  returns distance estimates, as opposed to actual paths that implement these estimates, and in the algorithm of <cit.> the coefficient β of the additive term is super-constant (specifically, polylogarithmic in n). 

In the current paper we address these issues, and devise an algorithm for (1 + ,β· W)-ASP for S × V with running time O((m +s n)n^ρ), for an arbitrarily small parameter ρ > 0, with β = (1/ρ)^O(1/ρ).
This algorithm does report paths, rather than just distance estimates. Note also that the additive term grows linearly with the local maximum edge weight, i.e., with the weight of heaviest edge on each particular source-destination shortest path, as opposed to the global  maximum edge weight W_max.
Finally, its coefficient β is significantly smaller than β_Elk = (1/ρ)^O(log (1/ρ)ρ), though it is admittedly still quite large[We are able to further decrease β to 2^O(1/ρ), at the expense of increasing the multiplicative stretch from 1+ to 3+.]. (The coefficient β_Coh of <cit.> depends polylogarithmically on n, while the coefficient β in <cit.> and here are independent of n.)  

We also extend an algorithm of Dor et al. <cit.> to weighted graphs. Specifically, the algorithm of <cit.> works for unweighted undirected graphs. For any parameter κ = 1,2,…, it provides an additive 2(κ - 1)-APASP in (n^2+1/κ) time. Our extension applies to weighted undirected graphs.
It computes additive 2(κ-1)W-approximation for all pairs shortest paths within the same time (n^2+1/κ), i.e., for any vertex pair u,v ∈ V, it produces a path of length at most d_G(u,v) + 2(κ - 1)· W(u,v), where W(u,v) is as in (<ref>). 

Note that the linear dependence of additive error on W is unavoidable, as an algorithm with stretch (1+,o(W)) can be translated into an algorithm with the same running time and with a purely multiplicative stretch of 1+.




 §.§ Parallel Setting

In the PRAM model, multiple processors are connected to a single memory block, and the operations
are performed in parallel by these processors. We will mostly be concerned with the Concurrent Read Concurrent Write (CRCW) PRAM model, 
that allows multiple processors to access any memory cell at any given round. The running time is measured by the number of rounds, and the work by
the number of processors multiplied by the number of rounds.

Early algorithms for these problems <cit.> require Ω(√(n)) parallel time.
Algorithms of <cit.>, that were discussed in Section <ref>,
can also be  applied in PRAM. They provide  (1+)-APASP in polylogarithmic time and (n^ω) work. The algorithm 
of Cohen <cit.>, for a parameter ρ > 0, solves (1+)-ASP for S × V in polylogarithmic time 
(log n)^O(log (1/ρ)ρ) and work ((m + n^1+ρ) s + m · n^ρ). 


This tradeoff was then improved in <cit.>, where the running time is 
(log n)^O(1/ρ), and the work is the same as in <cit.>. Further spectacular progress was recently achieved 
by <cit.>, who devised (1+)-SSSP algorithms with time (log n)^O(1) and work (m). Nevertheless, for (1+)-ASP problem from the set S ⊆ V of sources, one needs to run these algorithms in parallel from all the s sources. As a result, their work complexity becomes Θ̃(m s). 

To summarize, all existing solutions for the problem with polylogarithmic time have work complexity Ω(min{m · s,n^ω}). We devise the first algorithm with polylogarithmic time (log n)^O(1/ρ) and work complexity 
((m + n s) n^ρ), for an arbitrarily small constant ρ > 0. In other words,  our work complexity is within n^ρ, for an arbitrarily small constant ρ>0, close to the lower bound of Ω(m + ns). 
On the other hand, unlike algorithms of <cit.>, whose approximation guarantee is a purely multiplicative 1 +, for an arbitrarily small > 0, our approximation guarantee is (1+,β· W), with
β = (1/ρ)^O(1/ρ), and W as in (<ref>). 

Moreover, our result can, in fact, be viewed as a PRAM distance oracle. Specifically, following the preprocessing that requires 
time (log n)^O(1/ρ) and work (m n^ρ), our algorithm stores a compact data structure of size (n^1+ρ).
Given a query  vertex s, this data structure provides distance estimates d̂(s,v) for all v ∈ V, which satisfies (<ref>) in constant time and using work (n^1+ρ), where β = (1/ρ)^O(1/ρ).
Note that the distance oracle has size arbitrarily close to linear in n, its preprocessing time is polylogarithmic and preprocessing work is arbitrarily  close to linear in m, and the query time is constant and the query work is arbitrarily close to linear in n.
(Note that as the query provides distance estimates for n vertex pairs {(s,v) | v ∈ V}, its query work complexity must be Ω(n).) 





 §.§ Hopsets, Spanners and Emulators



From the technical viewpoint, these results are achieved via a combination of our new constructions of emulators, spanners and hopsets. 
For parameters α,β≥ 1, we say that a graph H=(V,E', w) is an (α,β)-hopset for a (weighted) graph G=(V,E, w), if by adding E' to the graph, every pair x,y∈ V has an α-approximate shortest path consisting of at most β hops; Formally,

    d_G(x,y)≤ d_G∪ H^(β)(x,y)≤α· d_G(x,y) ,

where d_G∪ H^(β) is the shortest path in G∪ H containing at most β edges. The parameter α is called the stretch, and β is the hopbound. 

We say that H is an (α,β)-emulator if for every x,y∈ V,

    d_G(x,y)≤ d_H(x,y)≤α· d_G(x,y)+β ,

and H is a spanner if it is an emulator and a subgraph of G.

Hopsets and near-additive spanners are fundamental combinatorial constructs, and play a major role in efficient approximation of shortest paths in various computational models. These objects have been extensively investigated in recent years <cit.>. The main interest is to understand the triple tradeoff between the size of the hopset (respectively, spanner), to the stretch α, and to the hopbound (resp., additive stretch) β. For algorithmic applications, it is also crucial to bound the construction time of the hopset/spanner/emulator.





We show near-additive spanners for weighted graphs, where the additive stretch for the pair x,y may depend also on the largest edge weight on the corresponding shortest path from x to y,  W(x,y). For a parameter 0<ρ<1, we devise an algorithm that constructs a (1+ϵ,β· W)-spanner of size O(n^1+1/2^1/ρ+ n/ρ) with β≤(1/ρ/ϵ)^O(1/ρ). We also show how to analyze the construction so that it yields smaller additive stretch, while increasing the multiplicative one. Specifically, we get a
(c,β· W)-spanner of same size as above, for every constant c>3, and with β= (1/ϵ)^O(1/ρ). 
Our emulators have a somewhat improved β. 
All of our results admit near-linear time algorithms, i.e., their running time is O(|E|n^ρ), for an arbitrarily small constant ρ>0.

 







 §.§ Technical Overview


We adapt the constructions of <cit.> of hopsets, spanners and emulators so that they are suitable for weighted graphs, and provide an improved additive stretch (or hopbound) β. The basic idea in all these constructions is to generate a random hierarchy of vertex sets V=A_0⊇ A_1⊇…⊇ A_k=∅, where for each 0≤ i<k-1, each element in A_i is included in A_i+1 with probability ≈ n^-2^i-k (one should think of k=1/ρ). We also refer to vertices at A_i as vertices at level i. For each v∈ V, the pivot p_i(v) is the closest vertex in A_i to v. Then the set of edges H is created by connecting, for every 0≤ i≤ k-1, every vertex v∈ A_i∖ A_i+1 to its bunch: all other vertices in A_i that are closer to it than p_i+1(v). One difference in our construction is that we also connect each vertex to all its (at most k) pivots. The main technical innovation in this work is the new analysis of this construction, yielding various hopsets, emulators and spanners that apply for weighted graphs, and admit improved parameters. (Previous constructions of spanners and emulators <cit.> applied only for unweighted graphs.)


The previous analysis of the stretch for some pair x,y∈ V goes roughly as follows. Divide the x-y path into intervals, and try to connect these intervals using low stretch paths in H (and for hopsets, also some of the graph edges, but with few hops). Each interval can either have a low stretch path; or fail, in which case that interval admits a nearby pivot (of some level i). Then, consider two failed intervals (the leftmost and rightmost ones), and try to find an x-y path via the pivots of these intervals. 







We note that this partitioning of the x-y path to equal size intervals (used in previous works), cannot work directly for weighted graphs, since it may not be possible to divide the path to  intervals of equal (or even near-equal) size. We provide a subtle adaptation of this technique so that it can handle weights. In particular, we distinguish between short and long distances: The sufficiently long distances may suffer a partition to un-equal intervals, as the induced error is dominated by the multiplicative stretch of  1+ϵ. For the short distances, we stop this partitioning when it becomes too ”expensive", and resort to an argument similar to the one in <cit.>, which has large multiplicative stretch (of roughly 2^1/ρ). However, at the point where we stop, that stretch can be accounted for by the additive stretch β· W.

An additional ingredient in our new analysis of H as an emulator/spanner for weighted graphs, given a pair x,y∈ V, is to iteratively find a vertex z on the x-y shortest path (sufficiently far from x) that admits in H a path with low multiplicative stretch from x. When there is no such z, we show that we can reach y with small additive stretch. This technique can be used to obtain the improved dependence of β on the parameter k=1/ρ.



Recall that emulators are insufficient for reporting paths. In particular, the approach of <cit.> was based on emulators, rather than on spanners, and it is not clear if these algorithms can be adapted to build spanners (for weighted graphs).
On the other hand, with our approach we can convert our constructions of emulators into constructions of spanners.  
Specifically, to build a spanner, we  must use  graph edges. So in order to connect vertices v∈ A_i∖ A_i+1 to the vertices in their bunch B(v), we need to add paths of possibly many edges in the graph (rather than a single edge, as for emulators/hopsets). 
To do this we connect every vertex v to all vertices in its half-bunch (see Section <ref> for its definition), as opposed to connecting it to all vertices in its full bunch. (The latter is the case in the construction of emulators.) This turns out to be sufficient to ensure that the union of all these paths does not contain too many edges. For this analysis we employ ideas of counting pairwise path intersections, developed in the context of distance preservers <cit.> and near-additive spanners and distance oracles for unweighted graphs <cit.>. We simplify this approach, and extend it to weighted graphs.







 §.§ Organization


In Section <ref> we describe the construction of our emulators and hopsets. In Section <ref> we analyze this construction, showing it provides emulators for weighted graphs.
In Section <ref> we describe the construction of our spanners for weighted graphs (proofs are deferred to Appendix <ref>) and use them for our centralized algorithms for the ASP problem.
In Section <ref> we provide  efficient implementations of our constructions, and use them in Section <ref> for solving ASP in PRAM, and for PRAM distance oracles.

Our hopsets and emulators with improved β appear in Appendices <ref> and <ref>.
In Appendix <ref> we devise an algorithm for pure additive APASP for weighted graphs. 





  §.§.§ Bibliographical note

Related results about (α,β)-spanners for unweighted graphs and (α,β)-hopsets with α≥ 3+ were achieved independently of us and simultaneously by <cit.>. 
In another submission <cit.> 

, an (1+)-ASP algorithm for S × V with |S| = n^r,
for some 0 < r ≤ 1. was devised. The running time of this algorithm in the centralized setting is (n^ω(r)), where
ω(r) is the rectangular matrix multiplication exponent. (n^ω(r) is the time required to multiply an n^r × n matrix by an n × n one.) In PRAM setting that algorithm runs in polylogarithmic time and  (n^ω(r)) work.
For graphs G = (V,E,w) and sets of sources  S ⊆ V of size s such that m + ns = o(n^2), the algorithms that we devise in the current submission are more efficient than in <cit.>.

Following our work, <cit.> devised algorithms for purely additive spanners (e.g., spanners with multiplicative stretch exactly 1) for weighted graphs. In their results, the additive term depends on the global maximal edge weight W_max, and the size of their spanners is always Ω(n^4/3) (the latter is unavoidable for purely additive spanners, due to a lower bound of <cit.>).





§ CONSTRUCTION


We use a similar construction to that of <cit.>. One difference is that every vertex connects to pivots in all levels. (Recall that the main difference is in the analysis.) 
Let G = (V, E, w) be a weighted graph with n vertices, and fix an integer parameter k ≥ 1.
Let ν = 1/(2^k-1).
Let A_0… A_k be sets of vertices such that A_0 = V, A_k = ∅, and for 0 ≤ i ≤ k-2, A_i+1 is created by sampling independently every element from A_i with probability q_i = n^-2^iν· 2^-2^i -1.
For every 0 ≤ i ≤ k-1, the expected size of A_i is:


    N_i = E[|A_i|] = n ∏_j=0^i-1q_j = n^1-(2^i-1)ν· 2^-2^i - i + 1


For every i ∈ [k-1], define the pivot p_i(v) to be the closest vertex in A_i to v, breaking ties by lexicographic order. For every u ∈ A_i \ A_i+1 define the bunch (see fig:bunch)

    B(u) = {v ∈ A_i | d_G(u, v) < d_G(u, A_i+1)}∪{p_j(u) | i < j < k } .

That is, the bunch B(u) contains all the vertices which are in A_i and closer to u than p_i+1(u), and at most k pivots.
We then define H = {(u, v)  :  u ∈ V, v ∈ B(u)}, where the weight of the edge (u, v) is set as the weight of the shortest path between u,v in G.





	
	The size of H is 
	
    |H| = O(kn + n^1+ν)



The proof of Lemma <ref> is similar to previous works, we include it for completeness in appendix <ref>.




§ NEAR-ADDITIVE EMULATORS FOR WEIGHTED GRAPH






In this section we will show that H as defined in Section <ref> is a (1 + ε,β· W)-emulator for weighted graphs. Note that the construction there does not depend on ε, and indeed, H will be an emulator for all values of 0<ε <1 simultaneously (with β=β(ε) depending on ε). 






Let G = (V, E) be a weighted graph with non-negative weights w:E→_+, recall that for x,y∈ V we have W(x,y) = max{w(e)  :  e ∈ P_xy} (where P_xy is a shortest path from x to y in G). Let k ≥ 1 and Δ > 3 be given parameters (think of Δ=3+O(k/ϵ)).


We begin by proving two lemmas, handling long and short distances, respectively. The first lemma asserts that pairs which are sufficiently far apart admit either a low stretch path, or a nearby pivot of a higher level.

	Fix Δ >3. Let 0 ≤ i < k and let x,y ∈ V such that d_G(x,y) ≥ (3 Δ) ^ iW(x,y). Then at least one of the following holds:
	
		
  * d_H(x, y) ≤ (1 + 4i/Δ - 3) d_G(x, y)
		
  * d_H(x, p_i+1(x)) ≤Δ/Δ - 3 d_G(x, y)
	
	(For i=k-1, the first item must hold since p_i+1 doesn’t exist).


	Denote W=W(x,y).
	The proof is by induction on i. For the base case i=0, if y ∈ B(x) then d_H(x,y)=d_G(x,y) and the first item holds. Otherwise, if x∈ A_1 then d_G(x,p_1(x))=0, so the second item holds. The last case is that x∈ A_0∖ A_1 and y∉ B(x), then by (<ref>) we have d_H(x, p_1(x)) =d_G(x, p_1(x)) ≤ d_G(x, y)≤Δ/Δ - 3 d_G(x, y), thus the second item holds. Assume the lemma holds for i and prove for i+1. Let x,y∈ V be a pair of vertices such that  d_G(x,y) ≥ (3 Δ) ^ i+1W(x,y)
	
	Divide the shortest path between x and y into J segments {L_j = [u_j, u_j+1]}_j ∈ [J] of length at least (3Δ)^iW and at most d_G(x,y)/Δ. It can be done as follows: define u_1=x, j=2 and walk on the shortest path from x to y. Define u_j as the first vertex which d_G(u_j-1, u_j) ≥ (3Δ)^iW or define u_j = y if d_G(u_j-1, y) < (3Δ)^iW. Increase j by 1 and repeat. Note that each segment has length at most (3Δ)^iW+W. Finally, we join the last two segments.
	The length of the last segment is at most (3Δ) ^ iW + W + (3Δ)^iW ≤ 3^i+1Δ^iW≤ d_G(x,y)/Δ.
	The length of any segment except the last is also at most (3Δ) ^iW + W ≤ d_G(x,y)/Δ.
	
	Apply the induction hypothesis for every segment L_j with parameter i. If for all the segments the first item holds, then first item holds for x, y and i+1, since
	
    d_H(x,y)    ≤∑_j∈ J d_H(u_j, u_j+1) 
    	≤∑_j ∈ J(1 + 4i/Δ - 3)d_G(u_j, u_j+1) 
       ≤ (1 + 4i/Δ - 3) d_G(x,y).

	
	Otherwise, for at least one segment the second item holds. Let L_l (resp., L_r-1) be the leftmost (resp., rightmost) segment for which the second item holds. 
	We have that the second item holds for the pair u_l,u_l+1, and by symmetry of the first item, the second item also holds for the pair u_r, u_r-1 with parameter i. Hence
	
	
    d_H(u_r, p_i+1(u_r)) ≤Δ/Δ - 3 d_G(u_r-1, u_r) ≤d_G(x, y)/Δ - 3 , 
    
    	d_H(u_l, p_i+1(u_l)) ≤Δ/Δ - 3 d_G(u_l, u_l+1)≤ d_G(x, y)/Δ - 3.

	
	Consider first the case that p_i+1(u_r) ∈ B(p_i+1(u_l)). In this case H contains the edge {p_i+1(u_l), p_i+1(u_r)}, so we have
	
    d_H   (p_i+1(u_l), p_i+1(u_r)) 
    	≤ d_G(p_i+1(u_l), u_l) + d_G(u_l, u_r) + d_G(u_r, p_i+1(u_r)).

	
	By the triangle inequality,
	
    d_H   (u_l, u_r) 
       ≤ d_H(u_l, p_i+1(u_l)) + d_H(p_i+1(u_l), p_i+1(u_r)) + d_H(p_i+1(u_r), u_r) 
       (<ref>)≤ 2d_H (u_l, p_i+1(u_l)) + d_G(u_l, u_r) + 2d_H(p_i+1(u_r), u_r) 
       (<ref>)≤4 d_G(x, y)/Δ - 3 + d_G(u_l, u_r).

	
	Thus, the distance between x and y in H,
	
    d_H(x, y) 
    	   ≤∑_j ∈ [J] d_H(u_j, u_j+1) 
       ≤∑_j=1^l-1(1 + 4 i/Δ - 3)d_G(u_j, u_j+1) + d_H (u_l, u_r) 
    	+ ∑_j=r^J(1 + 4 i/Δ - 3)d_G(u_j, u_j+1) 
       ≤(1 + 4 i/Δ - 3)d_G(x, u_l) + d_H (u_l, u_r) + (1 + 4 i/Δ - 3)d_G(u_r, y) 
       (<ref>)≤(1 + 4 i/Δ - 3)d_G(x, u_l) + 4d_G(x, y)/Δ - 3  + d_G (u_l, u_r) 
    	+ (1 + 4 i/Δ - 3)d_G(u_r, y) 
       ≤(1 + 4(i+1)/Δ - 3)d_G(x, y),

	therefore the first item holds.
	
	The other case is that p_i+1(u_r) ∉ B(p_i+1(u_l)). Then
	
    d_H(p_i+1(u_l), p_i+2(p_i+1(u_l))) ≤ d_G(p_i+1(u_l), p_i+1(u_r)) .

	We can bound the distance d_H(x, p_i+2(x)) by
	
    d_H   (x, p_i+2(x)) 
       ≤ d_G(x, u_l) + d_G(u_l, p_i+1(u_l)) + d_G(p_i+1(u_l), p_i+2(p_i+1(u_l))) 
       ≤ d_G(x, u_l) + d_G(u_l, p_i+1(u_l)) + d_G(p_i+1(u_l), p_i+1(u_r)) 
       (<ref>)≤ d_G(x, u_l) + d_G(u_l, p_i+1(u_l)) 
    	+ d_G(u_l, p_i+1(u_l)) + d_G(u_l, u_r) + d_G(p_i+1(u_r), u_r) 
       (<ref>)≤ d_G(x, y) + 3 d_G(x,y)/Δ - 3 = Δ/Δ - 3 d_G(x,y).

	Hence the second item holds.

The previous lemma is useful for vertices which are very far from each other, since for i = k-1 the first item must hold. For vertices which are close to each other, we will need the following lemma.


	Let 0 ≤ i < k and fix x,y ∈ V. Let 
	
	m =max{d_G(x, p_i(x)),d_G(y, p_i(y)),d_G(x,y)}. Then at least one of the following holds:
	
		
  * d_H(x,y) ≤ 5m
		
  * d_H(x, p_i+1(x)) ≤ 4m and d_H(y, p_i+1(y)) ≤ 4m
	
	(For i=k-1, the first item must hold since p_i+1 doesn’t exist).



	If p_i(y) ∈ B(p_i(x)) the first item holds, since
	
    d_H(x, y)    ≤ d_H(x, p_i(x)) + d_H(p_i(x), p_i(y)) + d_H(p_i(y), y) 
       ≤ d_G(x, p_i(x)) + d_G(p_i(x), x) + d_G(x, y) 
    	+ d_G(y, p_i(y)) + d_G(p_i(y), y) 
       ≤ 5m .

	
	If p_i(y) ∉ B(p_i(x)), then d_G(p_i(x), p_i+1(p_i(x))) ≤ d_G(p_i(x), p_i(y)), in this case the second item holds, as
	
    d_H(x, p_i+1(x)) 
    	   ≤ d_H(x, p_i(x)) + d_H(p_i(x), p_i+1(p_i(x))) 
       ≤ d_G(x, p_i(x)) + d_G(p_i(x), x) + d_G(x, y) + d_G(y, p_i(y)) ≤ 4m .

	
	The bound on d_H(y, p_i+1(y)) is symmetric.


We are now ready to prove the following theorem.




	For any weighted graph G = (V, E) on n vertices, and any integer k > 1, there exists H of size at most O(kn + n^1+1/(2^k - 1)), which is a (1+ε, β· W)-emulator for any 0<ε <1, where β = O( k/ε)^k-1.








	Fix Δ = 3 + 4(k-1)/ε, β = 10 (3 Δ)^k-1. Let x, y ∈ V, and W=W(x,y).
	If d_G(x, y) ≥ (3Δ)^k-1W, we can apply Lemma <ref> for x, y and i=k-1. Since p_k(x) does not exist, the first item must hold.
	Thus,
	
    d_H(x,y) ≤(1 + 4(k-1)/Δ - 3) d_G(x, y) = (1 + ε)d_G(x,y) .

	
	
	Otherwise, take the integer 0≤ i<k-1 satisfying (3Δ)^iW≤ d_G(x, y) < (3Δ)^i+1W (note that there must be such an i, since d_G(x,y)≥ W). Apply Lemma <ref> for x, y and i. If the first item holds, we will get 1+ε stretch as before.
	
	Otherwise, the second item holds, and we know that d_G(x, p_i+1(x)) ≤Δ/Δ-3d_G(x,y)≤ 2d_G(x,y) (using that k≥ 2). By symmetry of x,y in the first item of Lemma <ref>, we have d_G(y,p_i+1(y))≤ 2d_G(x,y) as well.
	Set j=i+1 and apply Lemma <ref> with x, y, j, noting that m≤ 2d_G(x,y). If the first item holds, we found a path in H from x to y of length at most 5m≤ 10 d_G(x,y)≤ 10 (3 Δ)^k-1W = β· W.
	
	If the second item holds, we increase j by one and apply Lemma <ref> again. We continue this procedure until the first item holds. The fact that the second item holds implies that the bound m (the maximal distance of x,y to the level j pivots) increases every iteration by a factor of at most 4.
	Since the first item must hold for j=k-1, the path we found is of length at most 10· 4^k-i-2 d_G(x,y) ≤ 10· 4^k-i-2· (3Δ)^i+1W, which is maximized for i=k-2. Hence the additive stretch is at most 10·(3Δ)^k-1W = O((9 + 12(k-1)/ε)^k-1 W), as required.



	We note that the analysis did not use the fact that the path from x to y is a shortest path. In particular, for every path P from x to y of length d, we can obtain a path in H of length at most (1+ε)· d+β· W(P), where W(P) is the largest edge weight in P.




§ NEAR-ADDITIVE SPANNERS FOR WEIGHTED GRAPHS


In this section we devise our spanners for weighted graphs. We first describe the new construction, that differs from that of Section <ref> in several aspects, which are required in order to keep the size of the spanner under control (and independent of W_max). In particular, since we add paths, rather than edges, between each vertex to other vertices in its bunch, we need to ensure the size of H is small enough. To do that, we use half-bunches rather than bunches to define H (see (<ref>) below), and show that there are few intersections between the aforementioned paths (see Lemma <ref>). One last ingredient is altering the sampling probabilities, so that the argument on intersection goes through. This approach refines and improves ideas from <cit.>.




  
Construction.
Let G = (V, E) be a weighted graph with n vertices, and fix an integer parameter k ≥ 3.
Let ν = 1/(4/3)^k-1.
Let A_0… A_k be sets of vertices such that A_0 = V, A_k = ∅, and for 0 ≤ i ≤ k-2, A_i+1 is created by sampling every element from A_i with probability q_i = n^-4^iν/3^i+1.
For every 0 ≤ i ≤ k-1, the expected size of A_i is:


    N_i = E[|A_i|] = n ∏_j=0^i-1q_j = n^1-ν/3∑_j=0^i-1(4/3)^j=n^1-((4/3)^i-1)ν .


For every i ∈ [k-1], define the pivot p_i(v) to be the closest vertex in A_i to v, breaking ties by lexicographic order. For every u ∈ A_i \ A_i+1 define the half bunch

    B_1/2(u) = {v ∈ A_i  :  d_G(u, v) < d_G(u, A_i+1)/2} .

Let H = {P_uv :  u ∈ V, v ∈ B_1/2(u) ∪{p_j(u) | i < j < k }}, where P_uv is the shortest path between u,v in G (if there is more than one, break ties consistently, by vertex id, say).


	For any weighted graph G = (V, E) on n vertices, and any integer k > 2, there exists H of size at most O(kn + n^1+1/((4/3)^k - 1)), which is a (1+ε, β· W)-spanner for any 0<ε <1, with β = O(k/ε)^k-1.



	
	For any weighted graph G = (V, E) on n vertices, and any integer k > 2, there exists H of size at most O(kn + n^1+1/((4/3)^k - 1)), which is a (3+ε, β· W)-spanner for any ε>0 with β =O(1+1/ε) ^ k-1.




Full proofs for both theorems are given in appendix <ref>.



§ EFFICIENT IMPLEMENTATION


Since we use very similar constructions to the ones in <cit.>, we can use their efficient implementations (connecting to all pivots, which is the difference between constructions, can be done efficiently in their framework as well). We consider here the standard model of computation, and the PRAM (CRCW) model.
Given a parameter 1/k<ρ<1/2, we will want poly-logarithmic parallel time and Õ(|E|· n^ρ) work / centralized time. This is achieved by adding additional ⌈ 1/ρ⌉ sets A_i, that are sampled with uniform probability n^-ρ, which in turn increases the exponent of β by an additive 1/ρ+1. (In the case of multiplicative stretch 1+ϵ, it also increases the base of the exponent in β.)

We summarize the efficient implementation results for hopsets and emulators in the following theorem.




	
	For any weighted graph G = (V, E) on n vertices, parameters k > 2 and 1/k<ρ<1/2, there is a randomized algorithm running in time Õ(|E|· n^ρ), that w.h.p. computes H of size at most O(kn + n^1+1/(2^k - 1)), such that for any 0<ε<1 this H is:
	
		
  * A (1+ε, β· W)-emulator with  β=O(k+1/ρ/ε) ^ k+1/ρ.
		
  * A (3+ε, β· W)-emulator with  β=O(1/ε) ^ k+1/ρ.
		
  * A (3+ε, β)-hopset with β = O(1/ε) ^ k+1/ρ.
		
		
	
	
	Given ε in advance, the algorithm can also be implemented in the PRAM (CRCW) model, in parallel time (log n/ε)^O(k+1/ρ) and work Õ(|E|· n^ρ), while increasing the size of H by a factor of O(log^*n).


For spanners, recall that in Section <ref> we have a somewhat different construction, and in the analysis we enforce a stricter requirement on the sampling probabilities q_i. To handle this, we start sampling with the uniform probability n^-ρ only when N_i≤ n^1-3ρ (and not when N_i≤ n^1-ρ like before). Now the bound of Claim <ref> still holds, as N_i/q_i^3≤ n even for these latter sets. The "price" we pay for waiting until N_i≤ n^1-3ρ is that the work will now be |E|· n^3ρ. Rescaling ρ by 3, we get the following.




	
	For any weighted graph G = (V, E) on n vertices, parameters k > 6 and 1/k<ρ<1/6, there is a randomized algorithm running in time Õ(|E|· n^ρ), that w.h.p. computes H of size at most O(kn + n^1+1/(2^k - 1)), such that for any 0<ε<1 this H is:
	
		
  * A (1+ε, β· W)-spanner with  β=O(k+1/ρ/ε)^ k+3/ρ.
		
  * A (3+ε, β· W)-spanner with  β=O(1/ε) ^ k+3/ρ.
	
	Given ε in advance, the algorithm can also be implemented in the PRAM (CRCW) model, in parallel time (log n/ε)^O(k+1/ρ) and work Õ(|E|· n^ρ), while increasing the size of H by a factor of O(log^*n).






§ ALMOST SHORTEST PATHS IN WEIGHTED GRAPHS


Given a weighted graph G=(V,E, w) with n vertices and a set S⊆ V of s sources, fix parameters k>6, 0<ε<1 and 0<ρ<1/6. Here we show that our hopsets, emulators and spanners can be used for a (1+ε,β· W)-approximate shortest paths for pairs in S× V, in various settings.

For the standard centralized setting, we first compute a (1+ε, β· W)-spanner H of size O(kn + n^1+1/(2^k - 1)) with β=O(k+3/ρ/ε) ^ k+3/ρ, in time Õ(|E|· n^ρ) as in Theorem <ref>. Next, for every u∈ S run Dijkstra's shortest path algorithm in H, which takes time O(s·(|E(H)|+nlog n)) = Õ(s· n^1+1/(2^k-1)). 

The total running time for computing (1+ε, β· W)-approximate shortest path for all S× V, is Õ(|E|· n^ρ+s· n^1+1/(2^k-1)). One may choose ρ=1/k and obtain the following.


	For any weighted graph G = (V, E) on n vertices, a set S⊆ V of s sources, and parameters k > 6 and 0<ε<1, there is a  randomized  algorithm running in time Õ(|E|· n^1/k+s· n^1+1/(2^k-1)), that computes (1+ε,β· W)-approximate shortest paths for all pairs in S× V, where
	β=(k/ε) ^ O(k).


We remark that there is a more general tradeoff by choosing ρ as a free parameter. In addition, if one desires improved additive stretch, simply use the (3+ε, β· W)-spanner with  β=ε ^ -O(k).





 §.§ PRAM Shortest Paths and Distance Oracles


Given a weighted graph G=(V,E, w) with n vertices, fix parameters k≥ 1, 0<ε<1 and 0<ρ<1/6. The first step in both settings (computing approximate shortest paths and distance oracles) is the same. We construct a (1+ε, β· W)-emulator G' of size O(kn + n^1+1/(2^k - 1))·log^*n with  β=O(k+1/ρ/ε) ^ k+1/ρ, in parallel time (log n/ε)^O(k+1/ρ) and work Õ(|E|· n^ρ) as in theorem-eff. Next, compute a (1+ε, β)-hopset H size O(n^1+1/(2^k - 1))·log^*n for G' with the same β = O(k+1/ρ/ε) ^ k+1/ρ within the same parallel time and work <cit.>.[We remark that even though the emulator and hopset have exactly the same construction, we run the hopset algorithm on G' and not on G, thus we get a different set of edges.] We store both G' and H.



  
Approximate Shortest Paths. 
For the sake of simplicity we will choose ρ=1/k.
Given a set S of s sources, for each source u∈ S run β rounds of the Bellman-Ford algorithm in the graph G'∪ H starting at u. In each round of Bellman-Ford, every vertex sends its neighbors the current distance estimate to u that it has, and they update their distance estimate if needed. Since G'∪ H is a sparse graph with Õ(n^1+1/(2^k - 1)) edges, with  Õ(n^1+1/(2^k - 1)) processors one can implement each iteration in PRAM (CRCW) in O(2^k) time (see <cit.> for more details). As we have only β rounds, the total parallel time for all the Bellman-Ford rounds from all vertices in S is (k/ε)^O(k), and the total work is Õ(s· n^1+1/(2^k - 1)).

As the error of the emulator is (1+ε,β· W), and the hopset has only multiplicative 1+ε stretch, the total error is only (1+O(ε),O(β· W). We thus have the following result.


	For any weighted graph G = (V, E) on n vertices, a set S⊆ V of s sources, and parameters k > 2 and 0<ε<1, there is a PRAM randomized  algorithm running in (log n/ε)^O(k) parallel time and using Õ(|E|· n^1/k+s· n^1+1/(2^k - 1)) work, that computes (1+ε,β· W)-approximate shortest paths for all pairs in S× V, where
	β=(k/ε) ^ O(k).


As above, we can get a more general tradeoff with the parameter ρ, and improve the additive stretch by using the hopsets and emulators from Sections <ref>,<ref>, albeit the multiplicative stretch will increase.



  
Distance Oracles.
Recall that we store the emulator G' and a hopset H for G'.
Whenever a query u∈ V arrives, we run β rounds of Bellman-Ford algorithm in the graph G'∪ H. As noted above, each round of Bellman-Ford can be implemented in PRAM (CRCW) in O(2^k) time using Õ(n^1+1/(2^k - 1)) processors. So the total parallel time for the query is O(k+1/ρ/ε) ^ k+1/ρ.  Rescaling ε, we get a (1+ε, O(k+1/ρ/ε) ^ k+1/ρ· W)-approximation.
We conclude that the properties of the distance oracle we devise are:

	
  * Has size O(kn + n^1+1/(2^k - 1))·log^*n.
	
  * Given query u∈ V, can report (1+ε, β· W)-approximation to all distances in {u}× V, with β=O(k+1/ρ/ε) ^ k+1/ρ.
	
  * Has query time O(k+1/ρ/ε) ^ k+1/ρ and Õ(n^1+1/(2^k - 1)) work.
	
  * The preprocessing time is (log n/ε)^O(k+1/ρ) and work Õ(|E|· n^ρ).





alpha















§ A (3+Ε,Β)-HOPSET


Here we show that the set H of Section <ref> serves as a  (3+ϵ,β)-hopset, for all 0<ϵ<12 simultaneously, with β=2^O(k·log(1/ϵ)).

Denote by d_G^(t)(u, v) the length of the shortest path between u, v in G that contains at most t edges.
The following lemma bounds the number of hops and the stretch of the constructed hopset:


	
	Fix any 0 < δ≤ 1/4 and any x,y ∈ V. Then for every 0 ≤ i ≤ k-1, at least one of the following holds:
	
	
		
  * d_G∪ H^(2 · (1/δ)^i - 1)(x, y) ≤ (3 + 12 δ/1 - 3 δ) d_G(x, y)
		
  * d_G∪ H^(1)(x, p_i+1(x)) ≤3/1-3 δ d_G(x, y)
	



	The proof is by induction on i. For the base case i=0, if y ∈ B(x), then the edge (x, y) was added to the hopset and the first item holds. If not, it means that d_G(x,y) ≥ d_G(x, p_1(x)).
	Because every vertex is connected by a direct edge to all its pivots, the second item holds (since the coefficient of the right hand side is between 3 and 12 for 0<δ≤ 1/4).
	
	Assume the claim holds for i, and we will prove it holds for i+1.  Partition the shortest path between x and y into J ≤ 1/δ segments {L_j = [u_j, v_j]}_j∈[J] each of length at most δ· d_G(x, y), and at most (1/δ - 1) edges {(v_j , u_j+1)}_j∈[J] between consecutive segments. We can use the following: setting u_1 = x, and for each j ∈ [J], set v_j as the vertex in the shortest path between u_j and y which is farthest from u_j, but still d_G(u_j, v_j) ≤δ· d_G(x, y).
	If v_j ≠ y, set u_j+1 as the vertex which follows v_j in the shortest path between x and y. Otherwise set u_j+1 = y. This partition satisfies our requirement J ≤ 1/δ because for every j ∈ [J-1], d_G(u_j, u_j+1) > δ· d_G(x, y) (otherwise, we could have chosen v_j as u_j+1).
	
	Next, apply the induction hypothesis for all the pairs (u_j, v_j) with parameter i.	
	If for all the pairs (u_j, v_j) the first item holds, we can show that the first item holds for (x, y) with parameter i+1.
	Consider the path from x to y which uses the guaranteed path in G∪ H of the first item for all the pairs (u_j, v_j), and the edges (v_j, u_j+1). The number of hops in this path is bounded by (1/δ)·(2(1/δ)^i - 1) + (1/δ - 1) ≤ 2 · (1/δ)^i+1 - 1. The length of the path is bounded by (using the induction hypothesis on each pair):
	
	
    d_G∪ H^(2(1/δ)^i+1-1)(x, y)    ≤∑_j∈[J](d_G∪ H^(2(1/δ)^i-1)(u_j, v_j) + d^(1)_G(v_j, u_j+1))
       ≤  (3 + 12 δ/1 - 3 δ)d_G(x, y) .

	
	Otherwise, there exist at least one segment for which the first item doesn't hold. Let l ∈ [J] be the smallest index so that only the second item holds for the pair (u_l, v_l). By the induction hypothesis
	
	
    d_G∪ H^(1)(u_l, p_i+1(u_l)) ≤3/1-3 δ d_G(u_l, v_l) ≤3δ/1-3 δ d_G(x, y).

	
	Since we added the edges (x,p_i+1(x)), (y,p_i+1(y)) to the hopset H, by the triangle inequality,
	
    d_G ∪ H^(1)   (x, p_i+1(x)) ≤ d_G(x, u_l) + d_G(u_l, p_i+1(u_l)) 
       ≤ d_G(x, u_l) +  3δ/1-3 δd_G(x, y), 
    
    	d_G ∪ H^(1)   (y, p_i+1(y)) ≤ d_G(y, u_l) + d_G(u_l, p_i+1(u_l)) 
       ≤ d_G(y, u_l) +  3δ/1-3 δd_G(x, y).

	
	If the edge (p_i+1(x), p_i+1(y)) exists in H, its length can be bounded by
	
	
    d_G ∪ H^(1)   (p_i+1(x), p_i+1(y)) 
       ≤ d_G∪ H^(1)(p_i+1(x), x) + d_G(x, y) +  d_G∪ H^(1)(y, p_i+1(y)).

	
	Thus, the distance between x and y using 3 hops is
	
	
    d   _G∪ H^(3)(x, y) 
       ≤ d_G ∪ H ^(1) (x, p_i+1(x)) + d_G ∪ H ^ (1)(p_i+1(x), p_i+1(y)) + d_G ∪ H^(1)(p_i+1(y), y) 
       (<ref>)≤ 2 d_G ∪ H ^(1) (x, p_i+1(x)) + d_G(x, y) + 2 d_G ∪ H^(1)(p_i+1(y), y) 
       (<ref>) + (<ref>)≤ 2(d_G(x, u_l) + 3δ/1-3 δ d_G(x, y)) + d_G(x, y) + 2 (d_G(y, u_l) 
    3δ/1-3 δ d_G(x, y)) 
       ≤  (3 + 12 δ/1 - 3 δ)d_G(x, y),

	
	therefore the first item holds.
	
	If (p_i+1(x), p_i+1(y)) ∉ H, then we know that 
	d_G ∪ H ^(1)(p_i+1(x), p_i+2(p_i+1(x))) ≤ d_G(p_i+1(x), p_i+1(y)). We can bound the distance d_G ∪ H^(1)(x, p_i+2(x)) using the triangle inequality:
	
	
    d   _G ∪ H^(1)(x, p_i+2(x)) 
       ≤ d_G(x, p_i+1(x)) + d_G(p_i+1(x), p_i+2(p_i+1(x))) 
       (<ref>)≤  2 d_G(p_i+1(x), x) + d_G(x, y) +  d_G(y, p_i+1(y)) 
       ≤ 2 (d_G(x, u_l) + 3δ/1-3 δ d_G(x, y)) + d_G(x, y) + d_G(y, u_l) 
    	+ 3δ/1-3 δ d_G(x, y)
       ≤ 3 d_G(x, y) + 9δ/1-3 δ d_G(x, y) =3/1-3 δd_G(x, y).

	
	Thus the second item holds.
	

We conclude by summarizing the main result of this section.

	
	For any weighted graph G = (V, E) on n vertices, and any k ≥ 1, there exists H of size at most O(kn + n^1+1/(2^k - 1)), which is a (3+ε, β)-hopset for any 0 < ε≤ 12, with β = 2(3 + 12/ε) ^ k-1.


	Let x, y ∈ V.
	Apply lemma <ref> for x, y with δ = ε/12 + 3ε and i=k-1. Since A_k = ∅, the first item must hold:
	
    d_G∪ H^(2(3 + 12/ ε)^k-1)(x, y) ≤ (3 + ε) d_G(x, y).




	Note that at its lowest, the hopbound is O(4^k), achieved with stretch 15.
 




§ A (3 + Ε,Β· W)-EMULATOR


In this section we show that the same H constructed in Section <ref> can also serve as a (3 + ε,β· W) emulator for weighted graphs, for all values of 0<ε<1 simultaneously.

Let G = (V, E) be a weighted graph 
and let k ≥ 1 and Δ > 3 be given parameters (think of Δ=3+O(1/ϵ)).
Fix a pair x,y∈ V. Define D_-1=0 and for any integer i≥ 0, let D_i = W(x,y) ·∑_j=0^iΔ ^ j.
We can easily verify that

    D_i+1 = Δ· D_i  + W(x,y).











	
	Let 0 ≤ i ≤ k and let x,y ∈ V such that d_G(x,y) ≤ D_i and d_H(x, p_i(x)) ≤2 Δ/Δ - 3 D_i-1. Define m = max{Δ D_i-1, d_G(x, y)}. Then at least one of the following holds:
	
		
  * d_H(x, y) ≤ (3 + 8/Δ - 3) m.
		
  * d_H(x, p_i+1(x)) ≤2 Δ/Δ - 3 D_i.
	



	The proof is by induction on i. For the base case i=0, if y ∈ B(x), the first item holds. Otherwise d_H(x, p_1(x)) ≤ d_G(x, y) ≤ W(x,y) = D_0, thus the second item holds.
	
	Assume the claim holds for i and prove for i+1. By the triangle inequality:
	
    d_H(y, p_i+1(y)) ≤ d_G(y,x) + d_G(x, p_i+1(x)).

	
	If p_i+1(y) ∈ B(p_i+1(x)), we have
	
    d_H(p_i+1(x), p_i+1(y)) ≤ d_G(p_i+1(x), x) + d_G(x, y) + d_G(y, p_i+1(y)).

	
	Thus, the distance between x and y is
	
    d_H   (x, y) 
       ≤ d_H (x, p_i+1(x)) + d_H(p_i+1(x), p_i+1(y)) + d_H(p_i+1(y), y) 
       (<ref>)≤ 2 d_H(x, p_i+1(x)) + d_G(x, y) + 2 d_H(p_i+1(y), y) 
       (<ref>)≤ 2 d_H(x, p_i+1(x)) + d_G(x, y) + 2(d_G(y,x) + d_G(x, p_i+1(x)))  
       ≤ 3 d_G(x, y) + 4 · 2 Δ/Δ - 3 D_i
       ≤(3 + 8/Δ - 3) m,

	therefore the first item holds.
	
	If p_i+1(y) ∉ B(p_i+1(x)), then we know that
	
	
    d_H(p_i+1(x), p_i+2(p_i+1(x))) ≤ d_G(p_i+1(x), p_i+1(y)) .

	We can bound the distance d_H(x, p_i+2(x)) as follows.
	
    d_H   (x, p_i+2(x)) 
       ≤ d_G(x, p_i+1(x)) + d_G(p_i+1(x), p_i+2(p_i+1(x))) 
       (<ref>)≤2 d_G(p_i+1(x), x) + d_G(x, y) +  d_G(y, p_i+1(y)) 
       (<ref>)≤ 2 d_H(x, p_i+1(x)) + d_G(x, y) + d_G(y,x) + d_G(x, p_i+1(x))  
       ≤ 2 d_G(x, y) + 3 · 2 Δ/Δ - 3 D_i 
       (<ref>)≤ 2 D_i+1 + 6/Δ - 3 D_i+1
        = 2 Δ/Δ - 3 D_i+1.

	Hence the second item holds.

We are now ready to state the result of this section.


	
	For any weighted graph G = (V, E) on n vertices, and any k ≥ 1, there exists H of size at most O(kn + n^1+1/(2^k - 1)), which is a (3+ε, β· W)-emulator for any ε>0 with β = O(1+1/ε) ^ k-1.




	Let x, y ∈ V.	Recall that P_xy is the shortest path between x and y in G, and fix Δ = 3 + 8/ε.	
	Initialize i = 0. Let z be the farthest vertex from x in P_xy satisfying d_G(x,z) ≤ D_i. Note the requirement d_H(x, p_0(x)) ≤2 Δ/Δ - 3 D_-1=0 holds since p_0(x)=x. Apply lemma <ref> on x,z and i. If the second item holds, we increase i by one, update z to be the last vertex in P(x, y) satisfying d_G(x,z) ≤ D_i, and apply the lemma again for x, z and i (since the second item held for i-1, we have that d_H(x, p_i(x)) ≤2 Δ/Δ - 3 D_i-1 indeed holds).
	
	Consider now the index i such that the first item holds (we must find such an index, since at i=k-1 there is no pivot in level k). If it is the case that d_G(x, y) ≥ D_i then since D_i - Δ D_i-1 = W(x,y), it must be that d_G(x, z) ≥Δ D_i-1, as otherwise we could have taken a further away z (recall that every edge on this path has weight at most W(x,y)). Therefore m = d_G(x,z) and we found a path in H from x to z with stretch at most 3 + 8/Δ - 3. Next we update x=z, i = 0 and repeat the same procedure all over again.
	
	The last remaining case is that we found an index i such that the first item holds but d_G(x, y) < D_i. Note that in such a case it must be that z = y. The path in H we have from x to y is of length at most (3+8/Δ - 3)· D_i=(3+ε)· D_i. As i≤ k-1 and D_k-1≤ 2Δ^k-1· W(x,y), we have that
	
    d_H(x,y)≤ 2(3+ε)· (3 + 8/ε) ^ k-1· W(x,y) ,

	which is our additive stretch β.
	










§ FULL PROOF OF LEMMA <REF>


If we order the vertices in A_i by their distance to u, it is easy to see that the number of vertices which are in A_i and closer than p_i+1(u) is bounded by a random variable sampled from a geometric distribution with parameter q_i.
Hence E[|B(u)|] ≤ k + 1/q_i = k + n^2^iν2^2^i + 1.
For u ∈ A_k-1, since p_k(u) doesn't exist, B(u) contains all the vertices in A_k-1.
The number of vertices in A_k-1 is a random variable sampled from binomial Distribution with parameters (n, ∏_j=0^k-2q_j)=(n,n^-(2^k-1-1)ν· 2 ^ -2^k-1-k+2).
Hence, the expected number of edges added by bunches of vertices in A_k-1 is

    E[|A_k-1|2]    ≤ E[|A_k-1|^2] = E[|A_k-1|]^2  + Var(|A_k-1|) 
        = n^2∏_j=0^k-2q_j^2 + n(1 - ∏_j=0^k-2q_j)∏_j=0^k-2q_j 
       ≤ n^2 - 2(2^k-1-1)ν· 2 ^ 2(-2^k-1-k+2) + n· 2^-2^k-1-k+2
       ≤ (n^1 + ν + n) 2 ^ 3-k.

Hence, the total expected number of edges in H is:

    ∑_i=0^k-2(N_i · n^2^iν· 2 ^ 2^i +1) + E[|A_k-1|^2]  + kn 
       = ∑_i=0^k-2(n^1+ν· 2 ^ -i+2) + E[|A_k-1|^2]  + kn 
       =O(kn + n^1+ν)






§ PROOFS OF THEOREMS <REF>,<REF>





 §.§ Size analysis

Recall the construction of H described in Section <ref>. Define the bunch B(u) as in (<ref>). The following lemma will be useful to bound the size of the spanner H.

	Fix 0≤ i≤ k-1. Let u,v,x,y∈ A_i be such that v∈ B_1/2(u) and y∈ B_1/2(x), and P_uv∩ P_xy≠∅, then all four points are in B(u), or all four are in B(x).


	Assume w.l.o.g. that P_uv is not shorter than P_xy. Let z∈ V be a point in the intersection of the two shortest paths, then
	
    d_G(u,x)    ≤ d_G(u,z)+d_G(z,x) ≤ d_G(u,v)+d_G(y,x) 
       ≤ 2 d_G(u,v)<d_G(u, A_i+1) ,
 
	
	so x∈ B(u). The calculation showing y∈ B(u) is essentially the same.

Define the shortest path between two vertices consistently, s.t. each subpath is also a shortest path. Therefore two shortest paths can have at most one common subpath.

Fix 0≤ i≤ k-2, and consider the graph G_i containing all the shortest paths P_uv with u∈ A_i and v∈ B_1/2(u). We claim that the number of edges in G_i is at most O(n+C_i), where C_i is the number of pairwise intersections between these shortest paths. This is because vertices participating in at most 1 path have degree at most 2, and each intersection increases the degree of one vertex by at most 2 (recall that shortest paths can meet at most once).

	[|C_i|]≤ O(n^1+ν).


	By Lemma <ref> each intersecting pair of paths P_uv and P_xy we have that all four points belong to the same bunch. Thus, each u∈ A_i can introduce at most |B(u)|^3 pairwise intersecting paths.
	Recall that |B(u)| is a random variable distributed geometrically with parameter q_i, so
	
    [|B(u)|^3]   =∑_j=1^∞ j^3· q_i·(1-q_i)^j-1
       ≤ q_i·∑_j=1^∞ (1-q_i)^j-1· j(j+1)(j+2)≤6/q_i^3 .

	Thus the expected number of intersections at level i is at most
	
    [∑_u∈ A_i|B(u)|^3]    ≤ O(N_i/q_i^3)=O(n^1-((4/3)^i-1)ν· (n^4^iν/3^i+1)^3) 
       =O(n^1+ν) .

	
	
	It remains to bound path intersections in the last level k-1. Recall that
	
    N_k-1= n^1-((4/3)^k-1-1)ν=n^1-((4/3)^k-1-1)/((4/3)^k-1)≤ n^(1 + ν)/4 .

	Since the random choices for each point are independent, we have by Chernoff bound that [N_k-1>2n^(1 + ν)/4]≤ e^-Ω(n^(1 + ν)/4), so with very high probability the last set A_k-1 contains O(n^(1 + ν)/4) points. It means that we have O(√(n^1 + ν)) paths connecting these points, and even if they all intersect, they can yield at most O(n ^ 1 + ν) intersections.


It remains to bound the number of edges to pivots. For every v ∈ V, p_i(v) is the closest vertex to v in A_i breaking ties by id. Therefore all the vertices in P_v,p_i(v) share the same pivot at level i. Thus we add at most one edge for each vertex at every level, and O(nk) edges overall.

We conclude that the size of H is at most O(k· n^1+ν) (we can slightly change the probabilities by introducing a factor of 2^-4^i/3^i+1 - 1 to obtain size O(kn+ n^1+ν), as we did before. 







 §.§ Proof of theorem <ref>



We use the corresponding analysis of the emulator from Section <ref>. The use of half-bunches instead of bunches creates the following version of Lemma <ref>.


	Fix Δ >5. Let 0 ≤ i < k and let x,y ∈ V such that d_G(x,y) ≥ (3 Δ) ^ iW(x,y). Then at least one of the following holds:
	
		
  * d_H(x, y) ≤ (1 + 8i/Δ - 5) d_G(x, y)
		
  * d_H(x, p_i+1(x)) ≤2Δ/Δ - 5 d_G(x, y)
	
	


The main difference in the proof is in (<ref>), which is replaced by

    d_H(p_i+1(u_l), p_i+2(p_i+1(u_l))) ≤ 2d_G(p_i+1(u_l), p_i+1(u_r)) .

The new bounds in the Lemma guarantee the calculations still go through. For Lemma <ref> which takes care of small distances, we have the following change, with a very similar proof.


	Let 0 ≤ i < k and fix x,y ∈ V. Let 
	
	m =max{d_G(x, p_i(x)),d_G(y, p_i(y)),d_G(x,y)}. Then at least one of the following holds:
	
		
  * d_H(x,y) ≤ 5m
		
  * d_H(x, p_i+1(x)) ≤ 7m
	



In the proof we set Δ=5+8(k-1)/ε. The rest of the calculations follow analogously, one change is that when iteratively applying Lemma <ref>, the bound m increases by a factor of 7 (rather than 4, as in Lemma <ref>), but as 7≤ 3Δ is still true, it does not change anything.



 §.§ Proof of theorem <ref>

The stretch analysis is very similar to that of the emulator from Section <ref>, the main difference is in the use of half-bunches rather than the full ones, but this will increase the distance to pivots by a factor of 2, and affect the additive stretch only. 
We follow the analysis and notation presented in Section <ref>, but with Δ>5. We replace Lemma <ref> with the following.

	
	Let 0 ≤ i ≤ k and let x,y ∈ V such that d_G(x,y) ≤ D_i and d_H(x, p_i(x)) ≤3Δ/Δ - 5 D_i-1. Define m = max{Δ D_i-1, d_G(x, y)}. Then at least one of the following holds:
	
		
  * d_H(x, y) ≤ (3 + 16/Δ - 5) m.
		
  * d_H(x, p_i+1(x)) ≤4 Δ/Δ - 5 D_i.
	


The main difference in the proof is in (<ref>), which is replaced by

    d_H(p_i+1(x), p_i+2(p_i+1(x))) ≤ 2d_G(p_i+1(x), p_i+1(y)) ,

since we use half-bunches. One can then follow the calculations in the proof of Lemma <ref>, and check that the altered constants used in the 2 cases above suffice.


The proof of Theorem <ref> is the same as the proof of Theorem <ref>, the only differences are taking Δ=5+16/ε (which affects the value of β) and using the bounds of Lemma <ref> rather than of Lemma <ref>. 



§ ALMOST ALL PAIRS SHORTEST PATHS FOR WEIGHTED GRAPHS


In this section we present an algorithm for computing approximate All Pairs Shortest Paths (APASP) for weighted graphs, with purely additive stretch proportional to the heaviest edge of the shortest path. The algorithm is based on <cit.>.

We use two well known algorithms. The first one is greedyHittingSet(V, S) which receives a set V and a collection S of subsets of V, and returns a subset of V that hits every element in S.
It was shown the greedy implementation has a running time of Õ(|S|· |V|) and results a hitting set which is at most Õ(1) bigger than the minimal (<cit.> the proof of  theorem 2.1). 

The other algorithm we use is dijkstra((V, E), δ̂, u) for finding the distance from u to all the other vertices in the graph (V, E). The n× n matrix δ̂ holds the current best distance estimates, and the weight of an edge e∈ E is taken from that matrix.The algorithm will also update the entries of δ̂ in the row and column corresponding to u, if they are smaller than the previous values. The running time of the algorithm is O(m + nlogn).

Denote by L_s(u) the set of s lightest neighbors of u (i.e., the neighbors which are connected to u by one of the s lightest edges touching u).



Denote by W(p) the heaviest edge in the path p, and by w(p) the total weight of all edges on p. Define δ̂_i to be the distance estimation after running dijkstra for every u ∈ D_i.

We prove the additive stretch by induction. The main difference in our analysis, compared to the one of <cit.>, is that we need to use the induction hypothesis on a path which is not necessary the shortest path between the two vertices. For that reason we are proving a stronger claim which applies to every path between two vertices.


	
	Consider an execution of Algorithm <ref>. Let 1 ≤ i ≤ k. For every u ∈ D_i, v ∈ V and every path p between u and v, the following holds 
    d_G(u, v) ≤δ̂_̂î(u, v) ≤ w(p) + 2(i - 1) · W(p).
 

	The proof is by induction on i. For i = 1, running dijkstra for u is the same as running dijkstra on the original graph since E_1 = E. Therefore d_G(u, v) = δ̂_̂1̂(u, v)≤ w(p) (for any path p).
	
	Assume the claim holds for i - 1 and prove for i.
	If all the edges of p are in E_i, then when running dijkstra from u the path p exists and the claim holds.
	
	Otherwise, let (x', x) be the edge in p which is not in E_i and is the closest to v.
	Because (x', x)∉ E_i, x must have a degree greater than s_i-1, and thus have a neighbor z ∈ D_i-1 (since x∈ A_i-1, and D_i-1 is a hitting set for it).
	Since the missing edge (x',x) is not among the lightest s edges touching x, while (x,z) is, we get that
	
    w(x, z) ≤ w(x, x') ≤ W(p).

	
	Denote by p_x, v the subpath of p from x to v and by p_u, x the subpath of p from u to x.
	
	When running dijkstra algorithm from u, the graph contains the edges (u, z) ∈{u}× V and (z, x)∈ E_i. By the choice of the edge (x, 'x) as the missing edge closest to v, all the edges of the path p_x,v are also contained in E_i, thus
	
    δ̂_i(u, v) ≤δ̂_i-1(u, z) + w(z, x) + w(p_x, v) (<ref>)≤δ̂_i-1(u, z) + W(p) + w(p_x, v).

	As z ∈ D_i-1, by applying the induction hypothesis for δ̂_i-1(z, u) = δ̂_i-1(u, z) with the path p_u, x∪{(x, z)} we get
	
    δ̂_i(u, v)
    	
    	   ≤  w(p_u, x∪{(x, z)}) + 2(i - 2) · W(p_u, x∪{(x, z)}) +  W(p) + w(p_x, v) 
       ≤  w(p_u, x) + w(x, z) + 2(i - 2) · W(p_u, x∪{(x, z)}) +  W(p) + w(p_x, v) 
       (<ref>)≤  w(p_u, x) + W(p) + 2(i - 2) · W(p) +  W(p) + w(p_x, v) 
        =  w(p_u, x) + w(p_x, v)  + 2(i - 1) · W(p) 
        =  w(p) + 2(i-1)W(p).



We now state formally the result of this section.


	Given a weighted graph G=(V,E, w) with n vertices and m edges, there is a deterministic algorithm running in time Õ(n^2 - 1/km^1/k), that returns distance estimations δ̂ such that for every u, v ∈ V,
	
    d_G(u, v) ≤δ̂(u, v) ≤ d_G(u, v) + 2(k-1)· W(u, v) .




	For the distance estimation, since D_k = V, it can be inferred directly from Lemma <ref> for i=k and the shortest path from u to v.
	
	The proof for the running time of the algorithm is very similar to the proof of theorem 4.1 from <cit.>.
	We first bound the sizes of D_i and E_i.
	Every set in the collection given to greedyHittingSet in iteration i is of size s_i, so |D_i|=O(nlogn/s_i). The size of E_i is O(n · s_i-1) as we take the lightest s_i-1 edges for every vertex.
	
	For every 2 ≤ i ≤ k, we run dijkstra |D_i| times on a graph with O(|E_i| + n) edges.
	Thus, the running time of  dijkstra algorithm for all u ∈ D_i is Õ(|D_i| · (|E_i| + n)) = Õ(n/s_i· n · s_i-1) =  Õ(n^2-1/km^1/k). For i=1, we run dijkstra on the full graph Õ(n/s_1) times, which results the same running time. As k = O(log n), the total running time of all execution of dijkstra algorithm is Õ(n^2-1/km^1/k).
		The hitting sets computations can be done in time Õ(n ^ 2 + m) by first sorting the edges by weight for every vertex.


