Nearly Work-Efficient Parallel Algorithm for Digraph Reachability

08/03/2018 - 12:00
Speaker: 
Seminar: 
מיקום: 
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 previously known parallel algorithm with both nearly linear work and nontrivial parallelism. This talk presents the first such algorithm. Specifically, this talk presents a randomized parallel algorithm for digraph reachability with work O(m*polylog(n)) and span O(n^{2/3}*polylog(n)), with high probability, where n is the number of vertices and m is the number of arcs.

The main technical contribution is an efficient Monte Carlo algorithm that, through the addition of O(n*polylog(n)) shortcuts, reduces the diameter of the graph to O(n^{2/3}*polylog(n)) with high probability. While there are existing algorithms that achieve similar guarantees, they are not computationally efficient; the sequential algorithms have running times much worse than linear. This talk presents a surprisingly simple sequential algorithm with running time O(m log^2(n)) that achieves the stated diameter reduction. Parallelizing that algorithm yields the main result, but doing so involves overcoming several additional challenges.