CS Paper Radar

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

Gary Hoppenworth, George Z. Li, Sepideh Mahabadi, Jakub Tarnawski

cs.DS ·submitted 2026-11-03 15:25 UTC · v1
theory

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 $Ω(\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).

Closest papers

Nearest neighbours by meaning across the whole index.

Square-Root Pass Semi-Streaming Algorithms for Digraph Problems

cs.DS ·2026-11-02 ·Prantar Ghosh, Amirhossein Janfaza
theory similarity 0.82
Abstract

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 the number of semi-streaming passes needed to solve directed $s,t$-reachability: there is an exponential gap---$Ω(\log n/\log \log n)$ vs $n^{1/2+o(1)}$---between the best-known lower and upper bounds. Several related fundamental digraph problems, e.g., topological sorting, acyclicity testing, and decomposition into strongly connected components (SCCs), are known to have the same semi-streaming pass lower bound. However, no $o(n/\text{polylog}(n))$-pass upper bound was known for any of them. Our main result achieves an $n^{1/2+o(1)}$-pass semi-streaming algorithm for each of these problems. As a corollary, we get algorithms with the same pass and space usage for a broad class of DAG problems that admit a certain form of dynamic program over a topological ordering. This class includes weighted single-source shortest paths, longest paths, max-outdegree+1 coloring, and constructing a lexicographically-first DFS (depth-first search) forest. Our algorithm for the last problem can be seen as a generalization of our results on topological sorting and acyclicity testing: recall that standard textbook algorithms for these problems use DFS as a subroutine. Our algorithms are optimal up to an $n^{o(1)}$ factor in passes under the reasonable conjecture that $s,t$-reachability requires $Ω(\sqrt{n})$ semi-streaming passes. However, using the fact that our algorithms can be parameterized by the number of passes taken by topological sorting or single-source reachability algorithms, we prove stronger lower bounds for some of the problems even under weaker conjectures.

0.28

Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness

cs.DS ·2026-11-03 ·Hector Tierno, Shuang Yang
theory similarity 0.72
Abstract

The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name, although the underlying quantity has long played a central role in shortcut set and parallel reachability. Notably, Bals et al. establish hardness for every polynomial-factor approximation in nearly-linear time for weighted digraphs. Yet they give $n^{1/2+o(1)}$-approximation in the unweighted regime with nearly-linear running time, and their conditional lower bounds rule out certain constants only, leaving open whether polynomial loss is necessary. We give a randomized algorithm that estimates the reachability diameter of an unweighted digraph within a factor $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an $n^{2/15-\varepsilon}$-approximation in $\widetilde{O}(m+n)$ time for every fixed $\varepsilon\in(0,2/15)$, establishing the necessity of polynomial loss for nearly-linear time algorithms.

0.25

Sparsification Framework for Directed Densest Subgraph

cs.DS ·2026-10-01 ·Slobodan Mitrović, Theodore Pan
similarity 0.72
Abstract

We develop a new approach for computing approximate directed densest subgraphs (DDS). Our main result is a sparsification procedure that reduces a directed graph $G$ on $n$ vertices to a graph with $n \cdot \text{poly} \log n$ edges while preserving enough structure to recover an approximate DDS of $G$. Instantiating this framework in several memory-constrained settings, we obtain the following improvements over the state of the art: In semi-streaming, we obtain a single-pass algorithm that computes a $(1-\varepsilon)$-approximate DDS. Previously, the only semi-streaming algorithm that computed a constant approximation of DDS was by Bahmani, Kumar, and Vassilvitskii (2012), providing a $0.5-\varepsilon$ approximation in $O(\log n)$ passes. Hence, our work completely closes the approximation gap between undirected and directed DS in the semi-streaming setting, matching the $(1-\varepsilon)$-approximate undirected DS algorithm by Esfandiari, Hajiaghayi, and Woodruff (2016). In the near-linear-memory MPC regime, we obtain an $O(1)$-round algorithm for $(1-\varepsilon)$-approximate DDS, improving over the $O(\sqrt{\log n})$-round $(0.5-\varepsilon)$-approximation algorithm of Mitrović and Pan (2024). In the sublinear-time setting, we obtain an algorithm using $\tilde{O}(n)$ time, space, and oracle queries to compute a $(1-\varepsilon)$-approximate DDS, improving over the $\tilde{O}(n^{1.5})$ time, space, and query algorithm of Esfandiari, Hajiaghayi, and Woodruff (2016).

0.08

Breaking Two Barriers for Dynamic Planar Reachability

cs.DS ·2026-10-09 ·Adam Karczmarz, Michał Włodarczyk
top venuetheory similarity 0.70
Abstract · To appear at SODA 2027

We consider the reachability problem in fully dynamic directed planar graphs: the graph undergoes edge updates (insertions and deletions) and we receive queries asking if one vertex is reachable from another. The current-best online algorithm for dynamic planar reachability spends worst-case time $\widetilde{O}(n^{2/3})$ per query/update [Subramanian, ESA '93]. This can be improved to $\widetilde{O}(n^{1/2})$ in the offline setting or when the embedding is fixed [Diks and Sankowski, ESA '07]. Our contribution is twofold: 1. We present the first algorithm that breaks the square-root barrier for dynamic planar reachability in the offline setting, obtaining time ${O}(n^{0.49})$ per query/update. This shows that the problem is easier than answering distance queries in a dynamic undirected planar graph, for which a conditional lower bound of $n^{1/2 - o(1)}$ is known [Abboud and Dahlgaard, FOCS '16]. Notably, this lower bound applies to both online and offline algorithms. 2. Second, in the general online setting we design a randomized data structure with amortized update and query time ${O}(n^{0.664})$. This is the first improvement upon the exponent $2/3$ in over three decades. The main engine behind our theorems is a new sparsification framework aimed at maintaining information about reachability. Specifically, we study digraphs through the lens of VC dimensionality of certain set systems. First, we design sparse reachability emulators for planar digraphs that preserve the VC dimension. Second, we utilize orderings with a low ``stabbing number'' [Chazelle and Welzl, Discrete Comput. Geom. '89] to compute subquadratic reachability emulators in subquadratic time whenever the VC dimension is bounded.

0.40

A Nearly Optimal Min-Cut Algorithm for Dynamic Streams

cs.DS ·2026-10-25 ·Yang P. Liu, Hoai-An Nguyen, Vihan Shah, David P. Woodruff
similarity 0.70
Abstract

We give an $\tilde{O}(n/\varepsilon)$-space algorithm for the minimum cut problem in dynamic streams, resolving the space complexity of streaming min-cut up to polylogarithmic factors. Ding, Garces, Li, Lin, Nelson, Shah, and Woodruff (ITCS 2025) obtained the same $\tilde{O}(n/\varepsilon)$ space bound for insertion-only streams, while prior to our work the best known bound even for unweighted dynamic streams was $\tilde{O}(n/\varepsilon^2)$, due to Ahn, Guha, and McGregor (PODS 2012). Our main technical contribution is an $\tilde{O}(n/\varepsilon)$-space for-each cut sketch in dynamic streams, which may be of independent interest. The construction applies to weighted graphs under general $\pmΔ$ updates, a stronger model than the standard dynamic-stream setting in which weighted edges are inserted and deleted in their entirety. Despite this stronger guarantee, our algorithm is surprisingly simple and relies on very little machinery. We also obtain applications to minimum $\ell_p$-norm $k$-partitioning for every fixed $k$, weighted correlation-clustering evaluation for two clusters, and for-each cut sketching in balanced directed graphs.

0.45

Partially Dynamic Single-Source Shortest Paths in Almost-Linear Time

cs.DS ·2026-10-05 ·Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang
similarity 0.69
Abstract · v2: Added a deterministic almost-linear-time incremental SSSP algorithm with efficient approximate path reporting

We study $(1+ε)$-approximate single-source distances in directed graphs with positive integer edge weights in $[1,W]$. For every $0<ε\le1$, we give deterministic data structures for either edge insertions or edge deletions with total update time $m^{1+o(1)}ε^{-1}\log W$, where $m\ge n$ bounds the total number of initially present and inserted edges. Both structures explicitly maintain approximate distance estimates, answer distance queries in constant time, and identify unreachable vertices exactly. The incremental structure additionally reports a simple $(1+ε)$-approximate source path $P$ in $O(|P|)$ time. Our decremental structure gives the first almost-linear-time algorithm. It improves the previous best randomized expected bound of $\widetilde O(\min\{n^2,mn^{2/3}\})$ against an oblivious adversary [BPW20]. Our incremental bound improves the $ε^{-B}$ dependence of the $B$-level recursive algorithm of [Liu26] to an explicit $ε^{-1}$ factor while retaining almost-linear dependence on $m$. Our algorithms use modified interior point methods. For edge deletions, we extend the single-pair distance framework of [vBCKLMPSS24] to all targets simultaneously. A shared potential and one dynamic minimum-ratio cut instance support global updates to the distance labels. Our main insight is that constant relative cut balance certifies approximate distances at every target. For edge insertions, we develop an analogous circulation-based formulation implemented through the dynamic minimum-ratio cycle structure of [CKLMP24]. We also give a black-box reduction from distance estimates to path reporting in incremental graphs, with $m^{1+o(1)}ε^{-1}\log W$ additional maintenance time. This reduction may be of independent interest.

0.21

Combinatorial Minimum Cost Flow in Almost-Linear Time on Dense Graphs

cs.DS ·2026-10-23 ·Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
similarity 0.68
Abstract · 101 pages

We give a combinatorial algorithm that computes an exact minimum-cost flow in $n^{2+o(1)}$ time. This is the first combinatorial improvement since Goldberg-Tarjan [GT87], and is almost optimal in dense graphs. All previous faster algorithms, including the almost-linear-time algorithm of Chen et al. [CKL+22], rely on interior-point methods. Our main conceptual contribution is a black-box reduction from exact minimum-cost flow on general graphs to its approximation on DAGs, with only an $n^{o(1)}$ loss on the running time. This reduction allows future work on combinatorial minimum-cost flow to focus on DAGs, typically much easier to handle than general graphs. Our $n^{2+o(1)}$-time algorithm follows by combining this reduction with a simple augmenting-path-based approximation algorithm on DAGs. The reduction is based on a new structural result, called a flow-cost-preserving DAG projection. Given an arbitrary directed graph, this construction produces a DAG that approximately preserves both the congestion of flows and their cost up to a small loss.

0.48

A Simple Subquadratic Cut Query Protocol for Directed Reachability

cs.DS ·2026-11-04 ·Henry Fleischmann, Sagnik Mukhopadhyay, Swagato Sanyal
similarity 0.68
Abstract · 17 + 22 pages

We study $s$--$t$ reachability in an unweighted directed graph on $n$ vertices, accessed through a directed cut oracle: given $S\subseteq V$, the oracle returns the number of edges directed from $S$ to $V\setminus S$. Directed cut functions are submodular, and reachability asks whether the minimum $s$--$t$ cut has positive value. This connects the problem to the query complexity of submodular function minimisation. Whether or not reachability can be solved in truly subquadratic query complexity has been an outstanding open question for a decade. We give a simple algorithmic blueprint with two randomised implementations. The first uses $\widetilde O(n^{9/5})$ outgoing-cut queries; the second improves this bound to $\widetilde O(n^{5/3})$. The common idea is to construct an alternative orientation with the same underlying undirected graph and vertex-wise degree imbalances, thereby preserving reachability. We first approximate the target imbalances using an averaging and rounding procedure, then correct the remaining error with a flow. An earlier manuscript, made available in August 2026 in an online AI repository, reports an $\widetilde O(n^{3/2})$ query bound. Our contribution is a simple and comprehensible alternative approach that already achieves a polynomial saving over quadratic query complexity.

0.54