# Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators

Preprint · Alexandr Andoni, Clifford Stein, Peilin Zhong

- Archive id: arxiv:1911.01956
- Published: 2019-11-05
- arXiv: https://arxiv.org/abs/1911.01956
- Source URL: https://arxiv.org/abs/1911.01956
- PDF: https://arxiv.org/pdf/1911.01956
- Provenance: arxiv

## Abstract

We present a $(1+\\varepsilon)$-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving $\\mathrm{poly}(\\log n)$ depth and $m\\mathrm{poly}(\\log n)$ work for $n$-nodes $m$-edges graphs. Although sequential algorithms with (nearly) optimal running time have been known for several decades, near-optimal parallel algorithms have turned out to be a much tougher challenge. For $(1+\\varepsilon)$-approximation, all prior algorithms with $\\mathrm{poly}(\\log n)$ depth perform at least $Ω(mn^{c})$ work for some constant $c\>0$. Improving this long-standing upper bound obtained by Cohen (STOC'94) has been open for $25$ years. We develop several new tools of independent interest. One of them is a new notion beyond hopsets --- low hop emulator --- a $\\mathrm{poly}(\\log n)$-approximate emulator graph in which every shortest path has at most $O(\\log\\log n)$ hops (edges). Direct applications of the low hop emulators are parallel algorithms for $\\mathrm{poly}(\\log n)$-approximate single source shortest path (SSSP), Bourgain's embedding, metric tree embedding, and low diameter decomposition, all with $\\mathrm{poly}(\\log n)$ depth and $m\\mathrm{poly}(\\log n)$ work. To boost the approximation ratio to $(1+\\varepsilon)$, we introduce compressible preconditioners and apply it inside Sherman's framework (SODA'17) to solve the more general problem of uncapacitated minimum cost flow (a.k.a., transshipment problem). Our algorithm computes a $(1+\\varepsilon)$-approximate uncapacitated minimum cost flow in $\\mathrm{poly}(\\log n)$ depth using $m\\mathrm{poly}(\\log n)$ work. As a consequence, it also improves the state-of-the-art sequential running time from $m\\cdot 2^{O(\\sqrt{\\log n})}$ to $m\\mathrm{poly}(\\log n)$.

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

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