Parallel Reachability in Almost Linear Work and Square Root Depth

Download PDF

In this paper we provide a parallel algorithm that given any n-node m-edge directed graph and source vertex s computes all vertices reachable from s with \tilde{O}(m) work and n^{1/2 + o(1)} depth with high probability in n . This algorithm also computes a set of \tilde{O}(n) edges which when added to the graph preserves reachability and ensures that the diameter of the resulting graph is at most n^{1/2 + o(1)}. Our result improves upon the previous best known almost linear work reachability algorithm due to Fineman which had depth \tilde{O}(n^{2/3}).
Further, we show how to leverage this algorithm to achieve improved distributed algorithms for single source reachability in the CONGEST model. In particular, we provide a distributed algorithm that given a n-node digraph of undirected hop-diameter D solves the single source reachability problem with \tilde{O}(n^{1/2} + n^{1/3 + o(1)} D^{2/3}) rounds of the communication in the CONGEST model with high probability in n. Our algorithm is nearly optimal whenever D = O(n^{1/4 - \epsilon}) for any constant \epsilon > 0 and is the first nearly optimal algorithm for general graphs whose diameter is \Omega(n^\delta) for any constant \delta.