Abstract
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{Es,n^ω}) time, where ω < 2.372 is the matrix multiplication exponent. Existing PRAM algorithms with polylogarithmic depth (aka time) require work Ω(min{Es,n^ω}).
In a bold attempt to achieve centralized time close to the lower bound of m + n s, Cohen [Edith Cohen, 2000] 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 [Edith Cohen, 2000] was improved in [M. Elkin, 2001], 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 [Edith Cohen, 2000; M. Elkin, 2001] 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 sv path. Hence our additive term depends linearly on a local maximum edge weight, as opposed to the global maximum edge weight in [Edith Cohen, 2000; M. Elkin, 2001]. Finally, our β = (1/ρ)^{O(1/ρ)}, i.e., it is significantly smaller than in [Edith Cohen, 2000; M. Elkin, 2001].
We also extend a centralized algorithm of Dor et al. [D. Dor et al., 2000]. 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) ∈ binom(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.
BibTeX  Entry
@InProceedings{elkin_et_al:LIPIcs.SWAT.2022.23,
author = {Elkin, Michael and Gitlitz, Yuval and Neiman, Ofer},
title = {{Almost Shortest Paths with NearAdditive Error in Weighted Graphs}},
booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages = {23:123:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772365},
ISSN = {18688969},
year = {2022},
volume = {227},
editor = {Czumaj, Artur and Xin, Qin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16183},
URN = {urn:nbn:de:0030drops161833},
doi = {10.4230/LIPIcs.SWAT.2022.23},
annote = {Keywords: spanners, hopset, shortest paths, PRAM, distance oracles}
}
Keywords: 

spanners, hopset, shortest paths, PRAM, distance oracles 
Collection: 

18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) 
Issue Date: 

2022 
Date of publication: 

22.06.2022 