Nearly Work-Efficient Parallel Algorithm for Digraph Reachability

26 Mar
Theory of Computation Seminar
Jeremy Fineman, Georgetown University
Monday, March 26, 2018 -
1:15pm to 2:15pm
Pierce Hall 213 (Brooks Room)

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 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.

Speaker Bio: 

Jeremy Fineman is an Associate Professor of Computer Science at Georgetown University. His main research interest is in algorithm design and analysis, with a focus on data structures, parallel algorithms, memory-efficient algorithms, and scheduling. He received his Ph.D. from MIT in 2009 and did a postdoc at CMU before starting at Georgetown in 2011.

Carol Harlow