2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @G.Bach The number of partitions is not known beforehand (depends on the cluster) but should be between 1 and maybe 1000. $\endgroup$ – FUZxxl Sep 1 '17 at 11:29
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.