Is there a good algorithm for this graph problem?

Question

There's an undirected graph with weights on edges (weights are non-negative integers and their sum isn't big, most are 0). I need to divide it into some number of subgraphs (let's say graph of 20 nodes to 4 subgraphs of 5 nodes each) in a way that minimizes sum of weights of edges between different subgraphs.

This sounds vaguely like the minimum cut problem, but not quite close enough.

In alternative formulation - there's a bunch of buckets, all items belong to exactly two buckets, and I need to partition buckets into bucket groups in a way that minimizes number of items in more than one bucket group. (nodes map to buckets, edge weights map to duplicate item counts)

Answer 1

This is the minimum k-cut problem, and is NP hard. Here's a greedy heuristic that will guarantee you a 2-1/k approximation:

While the graph has fewer than k components: 1) Find a min-cut in each component 2) Split the component with the smallest weight min-cut.

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