Algorithms cut passes for key directed graph problems to square root scale
Square-Root Pass Semi-Streaming Algorithms for Digraph Problems
Data Structures and Algorithms
Summary
Some important problems about analyzing directed graphs, like checking if you can travel from one point to another or sorting nodes in order, are very hard to solve quickly when you can only look at the graph a few times and have limited memory. The authors found new methods that reduce the number of times you need to scan the graph edges to about the square root of the number of nodes, which is much fewer than before. This helps solve these problems more efficiently in situations where memory is limited. Their methods also apply to related tasks like finding shortest paths and coloring nodes.
What this means in practice
- •For network schedulers: Process massive network flow graphs in limited memory by reducing the number of data passes needed to detect reachability and routing paths.
- •For database engineers: Implement more efficient algorithms for query optimization tasks that rely on directed acyclic graph analyses using fewer data scans and less memory.
A theory result. No direct application yet.
Authors
Prantar Ghosh, Amirhossein Janfaza
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.