# Massively Parallel Algorithms for Approximate Shortest Paths

Article · Michal Dory, Shaked Matar

- Archive id: arxiv:2412.06952
- Published: 2024-12-09
- Venue: Distributed Computing
- DOI: https://doi.org/10.1007/s00446-025-00482-y
- arXiv: https://arxiv.org/abs/2412.06952
- Citations: 0
- Source URL: https://arxiv.org/abs/2412.06952
- PDF: https://arxiv.org/pdf/2412.06952
- Provenance: arxiv

## Abstract

We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take $poly(\\log{\\log{n}})$ rounds in the near-linear memory MPC model. Our results are for unweighted undirected graphs with $n$ vertices and $m$ edges. Our first contribution is a $(1+ε)$-approximation algorithm for Single-Source Shortest Paths (SSSP) that takes $poly(\\log{\\log{n}})$ rounds in the near-linear MPC model, where the memory per machine is $\\tilde{O}(n)$ and the total memory is $\\tilde{O}(mn^ρ)$, where $ρ$ is a small constant. Our second contribution is a distance oracle that allows to approximate the distance between any pair of vertices. The distance oracle is constructed in $poly(\\log{\\log{n}})$ rounds and allows to query a $(1+ε)(2k-1)$-approximate distance between any pair of vertices $u$ and $v$ in $O(1)$ additional rounds. The algorithm is for the near-linear memory MPC model with total memory of size $\\tilde{O}((m+n^{1+ρ})n^{1/k})$, where $ρ$ is a small constant. While our algorithms are for the near-linear MPC model, in fact they only use one machine with $\\tilde{O}(n)$ memory, where the rest of machines can have sublinear memory of size $O(n^γ)$ for a small constant $γ\< 1$. All previous algorithms for approximate shortest paths in the near-linear MPC model either required $Ω(\\log{n})$ rounds or had an $Ω(\\log{n})$ approximation. Our approach is based on fast construction of near-additive emulators, limited-scale hopsets and limited-scale distance sketches that are tailored for the MPC model. While our end-results are for the near-linear MPC model, many of the tools we construct such as hopsets and emulators are constructed in the more restricted sublinear MPC model.

_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.