Algorithms for graph partitioning on the planted partition model

TLDR

The NP‑hard graph bisection problem seeks to split an undirected graph into two equal groups while minimizing cross‑edges, and the more general graph l‑partition problem extends this to l equal groups with the same objective. The authors introduce a simple, linear‑time algorithm for the graph l‑partition problem and analyze its performance on a random planted l‑partition model. In the planted model, n nodes are divided into l groups of size n/l, with intra‑group edges appearing with probability p and inter‑group edges with probability r<p. They prove that if p−r≥n^{−1/2+ϵ} for some constant ϵ, the algorithm recovers the optimal partition with probability 1−exp(−nΘ(ε)). © 2001 John Wiley & Sons, Inc.; Random Structures & Algorithms, 18:116–140, 2001.

Abstract

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