Algorithms for graph partitioning on the planted partition model

The NP-hard graph bisection problem is to partition the nodes of an undirected graph into two equal-sized groups so as to minimize the number of edges that cross the partition. The more general graph l-partition problem is to partition the nodes of an undirected graph into l equal-sized groups so as to minimize the total number of edges that cross between groups. We present a simple, linear-time algorithm for the graph l-partition problem and we analyze it on a random “planted l-partition” model. In this model, the n nodes of a graph are partitioned into l groups, each of size n/l; two nodes in the same group are connected by an edge with some probability p, and two nodes in different groups are connected by an edge with some probability r<p. We show that if p−r≥n−1/2+ϵ for some constant ϵ, then the algorithm finds the optimal partition with probability 1− exp(−nΘ(ε)). © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 116–140, 2001