High-Probability Parallel Transitive-Closure Algorithms

There is a straightforward algorithm for computing the transitive-closure of an n-node graph in $O(\log ^2 n)$ time on an EREW-PRAM, using $n^3 / \log n$ processors, or indeed with $M(n) / \log n$ processors if serial matrix multiplication in $M(n)$ time can be done. This algorithm is within a log factor of optimal in work (processor-time product), for solving the all-pairs transitive-closure problem for dense graphs. However, this algorithm is far from optimal when either (a) the graph is sparse, or (b) we want to solve the single-source transitive-closure problem. It would be ideal to have an $\mathcal{NC}$ algorithm for transitive-closure that took about e processors for the single-source problem on a graph with n nodes and $e \geqq n$ arcs, or about $en$ processors for the all-pairs problem on the same graph. While an algorithm that good cannot be offered, algorithms with the following performance can be offered. (1) For single-source, $\tilde{O}(n^\varepsilon )$ time with $\tilde O(en^{1 - 2\varepsil...