License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.23
URN: urn:nbn:de:0030-drops-161833
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16183/
Elkin, Michael ;
Gitlitz, Yuval ;
Neiman, Ofer
Almost Shortest Paths with Near-Additive Error in Weighted Graphs
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{|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 [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 s-v 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 Near-Additive Error in Weighted Graphs}},
booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages = {23:1--23:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-236-5},
ISSN = {1868-8969},
year = {2022},
volume = {227},
editor = {Czumaj, Artur and Xin, Qin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16183},
URN = {urn:nbn:de:0030-drops-161833},
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 |
