Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs

There are linear-time sequential algorithms for many fundamental problems related to digraph reachability. In contrast, the best parallel algorithms known for these problems, although fast, require a great many processors and, hence, require much more computation overall than the sequential algorithms. This contrast reflects a seemingly unavoidable reliance on transitive closure techniques in parallel algorithms for digraph reachability. To further understanding of the nature of the bottleneck, we present a collection of polylog-time reductions among reachability problems. These reductions use only linear processors and work for general graphs. Futhermore, for planar digraphs, we give polylog-time algorithms for the following problems: (1) directed ear decomposition, (2) topological ordering, (3) digraph reachability, (4) descendant counting, and (5) depth-first search. Our new algorithms use only a linear number of processors, and, hence, are the first to be within a polylog factor of optimal in their use of parallelism.