# Better Bounds for Semi-Streaming Single-Source Shortest Paths

Article · Sepehr Assadi, Gary Hoppenworth, Janani Sundaresan

- Archive id: arxiv:2507.17841
- Published: 2025-07-23
- Venue: Society for Industrial and Applied Mathematics eBooks
- DOI: https://doi.org/10.1137/1.9781611978971.184
- arXiv: https://arxiv.org/abs/2507.17841
- Citations: 0
- Source URL: https://arxiv.org/abs/2507.17841
- PDF: https://arxiv.org/pdf/2507.17841
- Provenance: arxiv

## Abstract

In the semi-streaming model, an algorithm must process any $n$-vertex graph by making one or few passes over a stream of its edges, use $O(n \\cdot \\text{polylog }n)$ words of space, and at the end of the last pass, output a solution to the problem at hand. Approximating (single-source) shortest paths on undirected graphs is a longstanding open question in this model. In this work, we make progress on this question from both upper and lower bound fronts: We present a simple randomized algorithm that for any $ε\> 0$, with high probability computes $(1+ε)$-approximate shortest paths from a given source vertex in \\\[ O\\left(\\frac{1}ε \\cdot n \\log^3 n \\right)~\\text{space} \\quad \\text{and} \\quad O\\left(\\frac{1}ε \\cdot \\left(\\frac{\\log n}{\\log\\log n} \\right) ^2\\right) ~\\text{passes}. \\\] The algorithm can also be derandomized and made to work on dynamic streams at a cost of some extra $\\text{poly}(\\log n, 1/ε)$ factors only in the space. Previously, the best known algorithms for this problem required $1/ε\\cdot \\log^{c}(n)$ passes, for an unspecified large constant $c$. We prove that any semi-streaming algorithm that with large constant probability outputs any constant approximation to shortest paths from a given source vertex (even to a single fixed target vertex and only the distance, not necessarily the path) requires \\\[ Ω\\left(\\frac{\\log n}{\\log\\log n}\\right) ~\\text{passes}. \\\] We emphasize that our lower bound holds for any constant-factor approximation of shortest paths. Previously, only constant-pass lower bounds were known and only for small approximation ratios below two. Our results collectively reduce the gap in the pass complexity of approximating single-source shortest paths in the semi-streaming model from $\\text{polylog } n$ vs $ω(1)$ to only a quadratic gap.

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