Answers are grounded in this paper and cite their sources.
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 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 n1/2+o(1) passes due to Jambulapati, Liu, and Sidford (2019), while the best lower bound is Ω(log n/loglog 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 O(n) space and n1/3+o(1) passes. Our algorithms are based on implicit hopsets, which are large hopsets that can be represented implicitly in 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).
No takes yet. Share an insight, caveat, or question.
Hoppenworth et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: