Skip to content
#edge computing Preprint

Semi-Streaming Reachability and Shortest Paths in $n^{1/3+o(1)}$ Passes

Nov 2026 · 0 citations
Computer Science

Abstract

In the semi-streaming model, the edges of an $n$-vertex graph arrive in a stream, and an algorithm makes multiple passes over that stream while using only $\widetilde{O}(n)$ space. The number of passes needed to compute single-source reachability in directed graphs is a long-standing open question in streaming algorithms, going back to Henzinger, Raghavan, and Rajagopalan (1998). The best known semi-streaming algorithm uses $n^{1/2+o(1)}$ passes due to Jambulapati, Liu, and Sidford (2019), while the best lower bound is $\Omega(\log n/\log\log n)$ passes due to Guruswami and Onak (2016). We give streaming algorithms for computing single-source reachability and shortest paths on $n$-vertex directed graphs using $\widetilde{O}(n)$ space and $n^{1/3+o(1)}$ passes. Our algorithms are based on implicit hopsets, which are large hopsets that can be represented implicitly in $\widetilde{O}(n)$ space. We introduce this notion and give new constructions for implicit hopsets with small hopbound. Along the way, we obtain new work-depth tradeoffs for parallel shortest paths in directed graphs, improving the recent result of Ashvinkumar, Bernstein, Probst Gutenberg, and Saranurak (2026).

View source

Similar papers

Preprint Nov 2026

Square-Root Pass Semi-Streaming Algorithms for Digraph Problems

We study directed graph problems in the semi-streaming model where we are restricted to $\widetilde{O}(n):=O(n\cdot \text{polylog}(n))$ space for processing the edge stream of an $n$-node graph and can make one or a few passes to solve the given problem. A longstanding open problem in multipass streaming is determining...

Prantar Ghosh, Amirhossein Janfaza · 0 citations
Preprint Nov 2026

Faster Semi-Streaming and Dynamic Approximate Maximum Weight Matchings in General Graphs: A Unified Framework

We study the $(1-\varepsilon)$-approximate maximum weight matching problem in general graphs with $n$ vertices and integer edge weights in $[1,W]$. For $W=n^{O(1)}$, we obtain faster algorithms in the semi-streaming and dynamic settings: (1) Semi-streaming: Deterministic $O(\varepsilon^{-2})$-pass and $O(\varepsilon^{-...

Jia-Le Chen · 0 citations
Preprint Oct 2026

A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed Graphs

In the restricted shortest paths problem, we are given an $n$-vertex $m$-edge directed graph $G$ whose edges are assigned two non-negative weights (or resources) called lengths and costs, a source vertex $s$, and a cost threshold $C$. The goal is to find, for each target vertex $t$, the length of the shortest $(s,t)$-p...

Vikrant Ashvinkumar · 0 citations
Sep 2026

Maximum Matching Size for Bounded Arboricity Graphs in the Dynamic Graph Stream Model using ~O}(n2/3) space

The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\varepsilon)(\alpha+2)$-approximation for the size of the maximum matching in a graph of arboricity at most $\alpha$. The algorithm uses $O(\varepsilon^{-4/3}\alpha^{4/3}n^{2/3} \text{polylog} n)$ space. For constant $\al...

A. Mcgregor · 0 citations
Preprint Oct 2026

Sublinear-Time and Semi-Streaming Algorithms for Path Cover and TSP

We give improved sublinear-time and semi-streaming approximation algorithms for maximum path cover, $(1,2)$-TSP, and Max-TSP. For each fixed $\eps>0$, our distance-query algorithm estimates the optimum cost of an $n$-vertex $(1,2)$-TSP instance from above within factor $2-\cstar+\eps=1.413184\ldots+\eps$, with high pro...

Sharareh Alipour, Ali Nowzari · 0 citations
Preprint Oct 2026

Breaking Two Barriers for Dynamic Planar Reachability

The first algorithm that breaks the square-root barrier for dynamic planar reachability in the offline setting is presented, obtaining time ${O}(n^{0.49})$ per query/update, which is the first improvement upon the exponent $2/3$ in over three decades.

A. Karczmarz, Michał Włodarczyk · 0 citations

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.