Is there a good algorithm for this graph task?

Question

There is an undirected graph with weights on the edges (weights are non-negative integers, but their sum is small, most of them are 0). I need to divide it into a number of subgraphs (say, a graph of 20 nodes to 4 subgraphs of 5 nodes each) in such a way as to minimize the sum of the weights of the edges between different subgraphs.

It sounds vague, like a minimal cut problem, but not quite enough.

In an alternative formulation, there are a bunch of buckets, all the elements belong to exactly two buckets, and I need to break the buckets into groups of the bucket in such a way as to minimize the number of elements in more than one bucket group. (display of nodes in buckets, display of border maps for duplicate counting of elements)

Answer 1

This is a minimal k-cut problem, and NP is difficult. Here's a greedy heuristic that guarantees you an approximation of 2-1 / k:

While the graph has less than k components: 1) Find the minimum cut in each component 2) Separate the component with the minimum minimum cut.

The problem is studied in this article: http://www.cc.gatech.edu/~vazirani/k-cut.ps