Nearly Work-Efficient Parallel Algorithm for Digraph Reachability
share
One of the simplest problems on directed graphs is that of identifying the set of vertices reachable from a designated source vertex. This problem can be solved easily sequentially by performing a graph search, but efficient parallel algorithms have eluded researchers for decades. For sparse high-diameter graphs in particular, there is no known work-efficient parallel algorithm with nontrivial parallelism. This amounts to one of the most fundamental open questions in parallel graph algorithms: Is there a parallel algorithm for digraph reachability with nearly linear work? This paper shows that the answer is yes. This paper presents a randomized parallel algorithm for digraph reachability and related problems with expected work Õ(m) and span Õ(n^2/3), and hence parallelism Ω̃(n^1/3), on any graph with n vertices and m arcs. This is the first parallel algorithm having both nearly linear work and strongly sublinear span. The algorithm can be extended to produce a directed spanning tree, determine whether the graph is acyclic, topologically sort the strongly connected components of the graph, or produce a directed ear decomposition of a strongly connected graph, all with similar work and span. The main technical contribution is an efficient Monte Carlo algorithm that, through the addition of Õ(n) shortcuts, reduces the diameter of the graph to Õ(n^2/3) with high probability. While both sequential and parallel algorithms are known with those combinatorial properties, even the sequential algorithms are not efficient. This paper presents a surprisingly simple sequential algorithm that achieves the stated diameter reduction and runs in Õ(m) time. Parallelizing that algorithm yields the main result, but doing so involves overcoming several other challenges.
READ FULL TEXT