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

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?

• @G.Bach The number of partitions is not known beforehand (depends on the cluster) but should be between 1 and maybe 1000. Sep 1, 2017 at 11:29

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.