Optimal Parallel Graph Algorithms

Optimal Parallel Construction of Hamiltonian Cycles and Spanning Trees in Random Graphs

Philip D. MacKenzie and Quentin F. Stout
EECS Department, University of Michigan

Abstract: We give tight bounds on the parallel complexity of some problems involving random graphs. Specifically, we show that a Hamiltonian cycle, a breadth first spanning tree, and a maximal matching can all be constructed in Θ(log^* n) expected time using n /log^*(n) processors on the CRCW PRAM. This is a substantial improvement over the best previous algorithms, which required Θ((loglog n)²) time and n log²(n) processors.

We then introduce a technique which allows us to prove that constructing an edge cover of a random graph from its adjacency matrix requires Ω(log^* n) expected time on a CRCW PRAM with O(n) processors. Constructing an edge cover is implicit in constructing a spanning tree, a Hamiltonian cycle, and a maximal matching, so this lower bound holds for all these problems, showing that our algorithms are optimal. This new lower bound technique is one of the very few lower bound techniques known which apply to randomized CRCW PRAM algorithms, and it provides the first nontrivial parallel lower bound for these problems. Notice that we simultaneously achieve the minimum time possible and linear speedup.

The lower bound proof is based on a simple analogue, which we call the Parallel Target Shooting problem. Imagine that there are n targets and n shooters. Each time a shooter shoots at a target, there is a fixed probability p, 0 < p < 1, that the shooter misses. This probability is independent of any other shots. The goal is to hit all of the targets at least once. Shooters shoot at targets in rounds, and between each round the results are observed and then it is decided how to reallocate shooters for the next round. More than one shooter can be shooting at a target in a given round.

Question: What is the minimal expected number of rounds needed until all targets are hit?
Answer: Ω(log^* n), which can be obtained if in each round the shooters are allocated as evenly as possible to the targets still unhit.

This is relevant to finding an edge cover because the processors have to search the adjacency table to find at least one edge per vertex. What is much less clear is how the PRAM can attain this time, since to just count the number of unhit targets takes Ω(log n /loglog n) time, even if a polynomial number of processors are used (this is because of the lower bound on parity). Thus work assignments have to be done probabilistically, and rather extensive analysis is needed to show that this expected time can be achieved.

Keywords: random graph, CRCW PRAM, parallel graph algorithm, edge cover, lower bounds, parallel target shooting, graph theory, SIMD shared memory parallel computer

Complete paper This paper appears in Proc. 5th ACM Symp. on Parallel Algorithms and Architectures (1993), pp. 224-229.

Related Work

Parallel computing:: An overview of my work in this area, and my papers.
Here is a somewhat whimsical explanation of parallel computing, a tutorial on parallel computing and a list of parallel computing resources
Ultrafast PRAM algorithms:: Ultrafast Parallel Algorithms and Reconfigurable Meshes surveys some of our work in this area. Sub-logarithmic algorithms for geometric problems appear in Constant-Time Geometry on PRAMs and Ultra-Fast Expected Time Algorithms