Lune

STOC2020Top-tier venue

Faster parallel algorithm for approximate shortest path

Jason Li

Abstract

We present the first m polylog(n) work, polylog(n) time algorithm in the PRAM model that computes (1 + )-approximate single-source shortest paths on weighted, undirected graphs. This improves upon the breakthrough result of Cohen [JACM'00] that achieves O(m 1+ 0 ) work and polylog(n) time. While most previous approaches, including Cohen's, leveraged the power of hopsets, our algorithm builds upon the recent developments in continuous optimization, studying the shortest path problem from the lens of the closely-related minimum transshipment problem. To obtain our algorithm, we demonstrate a series of near-linear work, polylogarithmic-time reductions between the problems of approximate shortest path, approximate transshipment, and ℓ 1 -embeddings, and establish a recursive algorithm that cycles through the three problems and reduces the graph size on each cycle. As a consequence, we also obtain faster parallel algorithms for approximate transshipment and ℓ 1 -embeddings with polylogarithmic distortion. The minimum transshipment algorithm in particular improves upon the previous best m 1+o(1) work sequential algorithm of Sherman [SODA'17].

To improve readability, the paper is almost entirely self-contained, save for several staple theorems in algorithms and combinatorics.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

25 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Undirected (1+ε)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms cites Parallel approximate undirected shortest paths via low hop emulators
  • Undirected (1+ε)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms cites Minor Sparsifiers and the Distributed Laplacian Paradigm
  • Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs cites Parallel approximate undirected shortest paths via low hop emulators
  • Minor Sparsifiers and the Distributed Laplacian Paradigm cites Parallel approximate undirected shortest paths via low hop emulators
  • Minor Sparsifiers and the Distributed Laplacian Paradigm cites Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
  • Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time cites Parallel approximate undirected shortest paths via low hop emulators
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers25

  1. Bipartite Matching in Nearly-linear Time on Moderately Dense GraphsJan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng et al.FOCS 2020 · 72 citations
  2. Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear TimeAaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol SaranurakFOCS 2021 · 27 citations
  3. Undirected (1+ε)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithmsVáclav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic et al.STOC 2022 · 22 citations
  4. Minor Sparsifiers and the Distributed Laplacian ParadigmSebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng et al.FOCS 2021 · 12 citations
  5. Ultrasparse Ultrasparsifiers and Faster Laplacian System SolversArun Jambulapati, Aaron SidfordSODA 2021 · 12 citations

Builds on1

  1. Parallel approximate undirected shortest paths via low hop emulatorsAlexandr Andoni, Clifford Stein, Peilin ZhongSTOC 2020 · 50 citations

Related papers

  1. Efficient construction of directed hopsets and parallel approximate shortest pathsNairen Cao, Jeremy T. Fineman, Katina RussellSTOC 2020 · 13 citations
  2. Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based ℓ1-Oblivious RoutingGoran Zuzic, Gramoz Goranci, Mingquan Ye, Bernhard Haeupler et al.SODA 2022 · 7 citations
  3. Parallel (1+ε)-Approximate Multi-Commodity Min-Cost Flow in Almost Optimal Depth and WorkBernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak et al.FOCS 2025 · 4 citations
  4. Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSPAdam Karczmarz, Wojciech Nadara, Marek SokolowskiSODA 2026
  5. Parallel Exact Shortest Paths in Almost Linear Work and Square Root DepthNairen Cao, Jeremy T. FinemanSODA 2023 · 4 citations
Dusk over the sea between two cliffs drawn in fine vertical lines