A multilevel algorithm for partitioning graphs

TLDR

Graph partitioning divides vertices into specified‑size sets with few cross edges, is NP‑complete, and is critical for parallel computation, circuit placement, and sparse matrix ordering. We propose a multilevel algorithm that approximates the graph by a hierarchy of progressively smaller graphs. The smallest graph is partitioned spectrally, the partition is lifted through the hierarchy, and a Kernighan‑Lin refinement is applied periodically, yielding an overall runtime linear in the original graph size. Experiments show the multilevel method achieves high‑quality partitions at lower cost than other advanced techniques.

Abstract

The graph partitioning problem is that of dividing the vertices of a graph into sets of specified sizes such that few edges cross between sets. This NP-complete problem arises in many important scientific and engineering problems. Prominent examples include the decomposition of data structures for parallel computation, the placement of circuit elements and the ordering of sparse matrix computations. We present a multilevel algorithm for graph partitioning in which the graph is approximated by a sequence of increasingly smaller graphs. The smallest graph is then partitioned using a spectral method, and this partition is propagated back through the hierarchy of graphs. A variant of the Kernighan-Lin algorithm is applied periodically to refine the partition. The entire algorithm can be implemented to execute in time proportional to the size of the original graph. Experiments indicate that, relative to other advanced methods, the multilevel algorithm produces high quality partitions at low cost.