Paper Info
Title
Nearly work-efficient parallel algorithm for digraph reachability
Abstract
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 O( m ) and span O( n 2/3 ), and hence parallelism Ω( m / n 2/3 ) = Ω( 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, i.e., span O( n 1−є ) for any constant єu003e0. 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, all with work O( m ) and span O( n 2/3 ). The main technical contribution is an efficient Monte Carlo algorithm that, through the addition of O( n ) shortcuts, reduces the diameter of the graph to O( 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, having sequential runtime Ω( mn Ω(1) ). This paper presents a surprisingly simple sequential algorithm that achieves the stated diameter reduction and runs in O( m ) time. Parallelizing that algorithm yields the main result, but doing so involves overcoming several other challenges.
Year
DOI
Venue
2017
10.1145/3188745.3188926
STOC '18: Symposium on Theory of Computing Los Angeles CA USA June, 2018
Keywords
Field
DocType
Parallel algorithm,randomized algorithm,graph search,reachability,shortcuts
Discrete mathematics,Randomized algorithm,Combinatorics,Parallel algorithm,Computer science,Directed graph,Reachability,Ear decomposition,Spanning tree,Sequential algorithm,Strongly connected component
Journal
Volume
ISSN
ISBN
abs/1711.01700
0737-8017
978-1-4503-5559-9
Citations 
PageRank 
References 
2
0.39
11
Authors
1
Name
Order
Citations
PageRank
Jeremy T. Fineman158736.10