Nearly Work-Efficient Parallel Algorithm for Digraph Reachability
Friday, October 15, 2021 11 AM to 12 PM
About this Event
6548 Forest Park Pkwy, St. Louis, MO 63112, USA
Dr. Jeremy Fineman
Associate Professor of Computer Science, Georgetown University
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 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. No efficient sequential or parallel algorithms were previously known for this problem. 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.
Event Details
See Who Is Interested
1 person is interested in this event
Dial-In Information
Register in advance for this meeting.
After registering, you will receive a confirmation email containing information about joining the meeting.
About this Event
6548 Forest Park Pkwy, St. Louis, MO 63112, USA
Dr. Jeremy Fineman
Associate Professor of Computer Science, Georgetown University
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 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. No efficient sequential or parallel algorithms were previously known for this problem. 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.