Tech Report CS-89-41
Heuristics for Parallel Graph-Partitioning
John E. Savage and Markus G. Wloka
December 1989 (revised January 29, 1991)
Graph partitioning is an important NP-complete problem with many applications. The problem is to partition vertices of a graph into two (nearly) equal-sized sets so that the number of edges joining the sets is minimal. It has applications in VLSI CAD, processor allocation, and many other areas. In this paper we show that the Kernighan-Lin and simulated annealing heuristics are logspace complete for the classes P and BPP, respectively, which means that they are hard to parallelize. We also describe a new parallel heuristic that on the 32K-processor CM-2 Connection Machine handles graphs with more than two million edges and gives in nine minutes partitions that are within 2% of the best ever found.
(complete text in pdf)