In parallel computation using parallel random access machines, very few efficient algorithms are known for problems involving directed graphs. The most demonstrative example of this situation is the problem of directed graph reachability. In its simplest form, the problem is to test whether a graph contains a directed path from a given vertex to another. The best sequential algorithms for the problem use simple graph searches and run in optimal linear time. In contrast, the best known parallel algorithm for the same problem computes the transitive closure of the given graph, and uses a superlinear number of processors. Therefore, there is a significant gap between the optimal sequential and the best known parallel complexities of the problem. This reliance on transitive closure techniques and the resulting inefficiency are also present in the best known parallel algorithms for many other fundamental problems in directed graph theory. The goal of this project is to remove the complexity bottleneck resulting from this undesirable reliance on transitive closure techniques. For fundamental problems on directed graphs, parallel algorithms will be designed that run in polylogarithmic time and use only a linear number of processors, and therefore, achieve an optimal complexity within a polylogarithmic factor.
