  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 known work-efficient parallel algorithm with
nontrivial parallelism. This amounts to one of the most fundamental open
questions in parallel graph algorithms: Is there a parallel algorithm for
digraph reachability with nearly linear work? This paper shows that the answer
is yes.
  This paper presents a randomized parallel algorithm for digraph reachability
and related problems with expected work $\tilde{O}(m)$ and span
$\tilde{O}(n^{2/3})$, and hence parallelism $\tilde{\Omega}(n^{1/3})$, on any
graph with $n$ vertices and $m$ arcs. This is the first parallel algorithm
having both nearly linear work and strongly sublinear span. The algorithm can
be extended to produce a directed spanning tree, determine whether the graph is
acyclic, topologically sort the strongly connected components of the graph, or
produce a directed ear decomposition of a strongly connected graph, all with
similar work and span.
  The main technical contribution is an \emph{efficient} Monte Carlo algorithm
that, through the addition of $\tilde{O}(n)$ shortcuts, reduces the diameter of
the graph to $\tilde{O}(n^{2/3})$ with high probability. While both sequential
and parallel algorithms are known with those combinatorial properties, even the
sequential algorithms are not efficient. This paper presents a surprisingly
simple sequential algorithm that achieves the stated diameter reduction and
runs in $\tilde{O}(m)$ time. Parallelizing that algorithm yields the main
result, but doing so involves overcoming several other challenges.
