2026-08-10T10:24:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16183 2024-03-06T10:57:06Z ddc:004 open_access

Almost Shortest Paths with Near-Additive Error in Weighted Graphs Elkin, Michael Gitlitz, Yuval Neiman, Ofer spanners hopset shortest paths PRAM distance oracles 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Elkin and Yuval Gitlitz and Ofer Neiman 2022 Is Part Of LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2022.23 urn:nbn:de:0030-drops-161833 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.23 eng https://creativecommons.org/licenses/by/4.0/legalcode