How can I partition a graph such that as few edges as possible cross partition boundaries?

Question

The following problem appeared while trying to distribute a program over a cluster of computers:

Given an undirected graph $G=(V,E)$ and an integer $n$, partition the vertices of $G$ into $n$ partitions $V_i$ of about equal size such that the number of edges crossing partition boundaries is minimised.

You can imagine $V$ as being chunks of a data set with $E$ indicating which chunks are related to what other chunks. When the computer operates on a chunk $v\in V_i$, it needs to access chunks from all $w\sim_E v$ and the performance is better if as many $w$ as possible are in the same partition $V_i$. The chunks are all of equal size and it is important that each partition $V_i$ contains about the same amount of them.

How can I a) model and b) approximate a good solution for this problem?

Answer 1

Your problem is known as graph partition. Apart from $n$, the problem has a parameter $\epsilon \geq 0$, and it is required that each part have size at most $(1+\epsilon)|V|/n$. The Wikipedia article mentions several relevant algorithms. The case $n = 2$ is known as minimum bisection when the parts are required to be exactly equal, and this is a well-known special case.

Answer 2

It should be noted that even the simplest case (minimum bisection) problem is NP-Hard. Look at the following articles:

"REDUCIBILITY AMONG COMBINATORIAL PROBLEMS" by Richard M. Karp

"Some Simplified NP-Complete Graph Problems" by M. R. Garey and D. S. Johnson