A natural way of solving the single source reachibility problem (where one is required to output the list of vertices that are reachable from a given vertex in a given digraph) is to compute the transitive closure of the graph (which is essentially equivalent to computing matrix multiplication). This work suggests an alternative (randomized) algorithm, which relies on finding shortcuts in the digraph. (This alternative is crucial in the parallel setting, since in the standard sequential model one can solve single source reachability in linear time by a straightforward search (e.g., BFS).)
The key observation is that, assuming the Matrix Multiplication exponent is 2 (i.e., $\omega=2$), $O(\log n)$-shortcuts, can be found in time that is almost linear in the size of the transitive closure, although the size of the transitive closure may be essentially as large as the digraph. In contrast, the best known algorithm for finding the transitive closure requires significantly more time than its size (when the graph is sparse), and such a result is conjectured to be optimal (see The Time Complexity of Fully Sparse Matrix Multiplication by Abboud et al. More generally, for any $d\geq3$ and transitive closure of size $T$, the $d$-shortcuts are found in time $\tildeO(T^{(d+2)\omega/2(d+1)})$, whereas the best known algorithm runs in time $T^{(4/3)+o(1)}$.)
Randomization is used to get an estimate of the size of the transitive closure and for obtaining an adequate hitting set. Specifically, this set is required to neighbor all vertices whose degree in the transitive closure exceeds a given value Delta and yet have relatively few incident edges in the transitive closure (i.e., at most a $1/Delta$ fraction of the edges of the transitive closure).
A $d$-shortcut of a directed graph $G=(V,E)$ is a subset of edges drawn from the transitive closure $TC(G)$ whose addition reduces the graph diameter to at most $d$. In the special case $d=1$, computing a $1$-shortcut is \emph{equivalent} to computing the transitive closure. For larger values of $d$, a lower bound of [Hesse, SODA 2003] shows that $n^{\delta}$-shortcuts, for small constants $\delta>0$, still require computing a large fraction of the edges of $TC(G)$, suggesting that shortcut construction may remain as hard as the transitive closure even in this regime. Consequently, since $\tilde{O}(d)$-depth parallel reachability algorithms rely on computing $d$-shortcuts, achieving $\tilde{O}(1)$ depth has so far required computing the full transitive closure. Assuming that matrix multiplication has exponent $\omega=2$, it has been conjectured by [Abboud et al., SODA 2024] that computing $TC(G)$ requires $T^{4/3-o(1)}$ time where $T=|TC(G)|$.
In this work, we bypass the transitive closure barrier for $\tilde{O}(1)$-depth parallel reachability. We introduce a hierarchy of $d$-shortcut constructions that already circumvents this barrier for $d \ge 3$. Our approach yields a $\tilde{O}(1)$-depth parallel reachability algorithm with total work $\tilde{O}(T^{\omega/2})$, which becomes $\tilde{O}(T)$ when $\omega=2$, improving over the conjectured $T^{4/3}$ barrier for transitive closure. For the current value of $\omega$, this corresponds to $\tilde{O}(T^{1.18})$ work, improving upon the current $T^{1.3459}$ sequential time bound transitive closure by Abboud et al. Thus, although $\tilde{O}(1)$-shortcuts might be almost as dense as the full transitive closure, they can nevertheless be computed significantly faster.