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

Categories: cs.DS

Parallel Reachability in Almost Linear Work and Square Root Depth