CS Paper Radar

Square-Root Pass Semi-Streaming Algorithms for Digraph Problems

Prantar Ghosh, Amirhossein Janfaza

cs.DS ·submitted 2026-11-02 18:35 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-11-03 ·Gary Hoppenworth, George Z. Li, Sepideh Mahabadi, Jakub Tarnawski
theory similarity 0.82
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).

0.20

Sparsification Framework for Directed Densest Subgraph

cs.DS ·2026-10-01 ·Slobodan Mitrović, Theodore Pan
similarity 0.69
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

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

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.68
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24

Strong Connectivity Oracle for Multiple Failures via Rooted Flow-Augmentation

cs.DS ·2026-11-06 ·Aditya Anand, Thatchaphol Saranurak, Benyu Wang
published similarity 0.67
Abstract · SODA 2027

We present a significantly improved $k$-fault-tolerant strong connectivity oracle, one of the most basic data structures on a directed graph $G$ that, given any set $F$ of failed edges of size $|F|\le k$, answers whether $G \setminus F$ is strongly connected. For every constant $k$, our oracle only uses $n^{1+o(1)}$ space and $n^{o(1)}$ query time. No prior result can achieve $o(n^{2})$ space and $o(n)$ query time, \emph{even when $k=2$}. Previous oracles either require $Ω(n)$ query time [BCR18], or $Ω(n^2)$ space [vdBS19]. Our main technical contribution is a \emph{rooted} version of the highly successful flow augmentation technique, which may be of independent interest. Given a directed graph $G$, an integer $k$, and a source vertex $s$, we can sample a set of edges $A$ such that each minimal $s$-rooted cut of size at most $k$ becomes an $s$-rooted min-cut in $G + A$ with probability $2^{-poly(k)}n^{-o(1)}$.

0.57

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

cs.DS ·2026-11-03 ·Hector Tierno, Shuang Yang
theory similarity 0.66
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

Improved Pass Complexity for Semi-Streaming Matching in General Graphs via Budgeted Price Approach

cs.DS ·2026-10-15 ·Tatsuya Terao
similarity 0.66
Abstract · 11 pages

We present a simple deterministic semi-streaming algorithm that computes a $(1-\varepsilon)$-approximate maximum matching in general graphs in $O(1/\varepsilon^{2})$ passes. This matches the pass complexity of the auction algorithm of Assadi, Liu, and Tarjan~[SOSA'21] for bipartite graphs, and answers Open Question~2 of Assadi~[SOSA'24 \& TheoretiCS'25]. Our approach, which we call the \emph{budgeted price approach}, is very different from the previous $\mathrm{poly}(1/\varepsilon)$-pass semi-streaming algorithms for $(1-\varepsilon)$-approximation of matching in general graphs and improves their pass complexity. All previous approaches are augmenting-path-based and use $O(1/\varepsilon^{19})$ passes by Fischer, Mitrović, and Uitto~[STOC'22], $O(1/\varepsilon^{6})$ passes by Mitrović, Mukherjee, Sankowski, and Sheu~[ICALP'25], and $O(1/\varepsilon^{4})$ passes by Izumi, Kitamura, and Yamaguchi~['25].

0.26

Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs

cs.DS ·2026-09-26 ·Daniel Lokshtanov, Saket Saurabh, Jie Xue
theory similarity 0.66
Abstract

We consider Directed Feedback Vertex Set on planar digraphs, parameterized by the solution size $k$. We give a randomized algorithm with one-sided error running in time $(2+\sqrt5)^k n^{O(1)}= 4.24^k n^{O(1)}$, and a deterministic algorithm running in time $8.04^k n^{O(1)}$. Both algorithms use polynomial space. To the best of our knowledge, these are the first single-exponential fixed-parameter algorithms for Directed Feedback Vertex Set on planar digraphs. This contrasts with general digraphs, where the best known algorithms run in time $2^{O(k\log k)}(n+m)$, and whether a $2^{o(k\log k)}n^{O(1)}$-time algorithm exists remains a major open problem. Our main tool is an exact Euler-type counting identity for plane digraphs. It shows that every small solution must carry a large share of the vertices whose in- and out-arcs alternate in the embedding, while solutions avoiding such vertices can be computed by reducing to Directed Feedback Arc Set, which is known to be solvable in polynomial time on planar digraphs via the Lucchesi-Younger theorem.

0.38