Metraipolis › archive › dc_c66c930be2a3
Square-Root Pass Semi-Streaming Algorithms for Digraph Problems — arXiv:2611.03594
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03594
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:45:49.720Z
- SHA-256 of the archived text
ac9f128ff34e39d840c4faa902e7cc4050cd4aa1b7161fc1b7b5d48218c33781- Stable URL of this page
https://metraipolis.com/documento/dc_c66c930be2a3
How to cite
Square-Root Pass Semi-Streaming Algorithms for Digraph Problems — arXiv:2611.03594 — arXiv (en), https://arxiv.org/abs/2611.03594 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c66c930be2a3 (Metraipolis archive dc_c66c930be2a3, sha256 ac9f128ff34e39d840c4faa902e7cc4050cd4aa1b7161fc1b7b5d48218c33781)
BibTeX
@misc{dcc66c930be2a3,
title = {Square-Root Pass Semi-Streaming Algorithms for Digraph Problems — arXiv:2611.03594},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03594},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c66c930be2a3; sha256 ac9f128ff34e39d840c4faa902e7cc4050cd4aa1b7161fc1b7b5d48218c33781},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03594. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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---$\Omega(\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 $\Omega(\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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.03594 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:07:52.263Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).