HIGH-PROBABILITY PARALLEL TRANSITIVE-CLOSURE ALGORITHMS

There is a straightforward algorithm for computing the transitive-closure of an n-node graph in O(log2 n) time on an EREW-PRAM, using n3/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 NC algorithm for transitive-closure that took about e processors for the single-source problem on a graph with n nodes and e greater-than-or-equal-to 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, O(n-epsilon) time with O(en1-2-epsilon) processors, provided e greater-than-or-equal-to n2-3-epsilon, and (2) for all-pairs, O(n-epsilon) time and O(en1-epsilon) processors, provided e greater-than-or-equal-to n2-2-epsilon-1. Each of these claims assumes that 0 < epsilon greater-than-or-equal-to 1/2. Importantly, the algorithms are (only) high-probability algorithms; that is, if they find a path, then a path exists, but they may fail to find a path that exists with probability at most 2-alpha-c, where alpha is some positive constant, and c is a multiplier for the time taken by the algorithm. However, it is shown that incorrect results can be detected, thus putting the algorithm in the "Las Vegas" class. Finally, it is shown how to do "breadth-first-search" with the same performance as can be achieved for single-source transitive closure.