# Almost Shortest Paths with Near-Additive Error in Weighted Graphs

Article · Michael Elkin, Yuval Gitlitz, Ofer Neiman

- Archive id: arxiv:1907.11422
- Published: 2019-07-26
- DOI: https://doi.org/10.4230/lipics.swat.2022.23
- arXiv: https://arxiv.org/abs/1907.11422
- Citations: 8
- Source URL: https://arxiv.org/abs/1907.11422
- PDF: https://arxiv.org/pdf/1907.11422
- Provenance: arxiv

## 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\\subseteq V$. We study the problem of computing {\\em almost shortest paths} (ASP) for all pairs in $S \\times 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$ . 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^ω\\})$. 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) \\in S\\times V$, it provides a path of length $\\hat{d}(s,v)$ that satisfies $\\hat{d}(s,v) \\le (1+ε)d\_G(s,v) + β\\cdot 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 {\\em local} maximum edge weight, as opposed to the global maximum edge weight in previous works. Finally, our $β= (1/ρ)^{O(1/ρ)}$. We also extend a centralized algorithm of Dor et al. \\cite{DHZ00}. For a parameter $κ= 1,2,\\ldots$, this algorithm provides for {\\em unweighted} graphs a purely additive approximation of $2(κ-1)$ for {\\em all pairs shortest paths} (APASP) in time $\\tilde{O}(n^{2+1/κ})$. Within the same running time, our algorithm for {\\em weighted} graphs provides a purely additive error of $2(κ- 1) W(u,v)$, for every vertex pair $(u,v) \\in {V \\choose 2}$, with $W(u,v)$ defined as above. On the way to these results we devise a suit of novel constructions of spanners, emulators and hopsets.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.