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)

Well, to minimize the sum of edges between the subgraphs is the same as to maximize the sum of edges within subgraphs. What exactly are the constraints for splitting the graph? — Hamish Grubijan
Do you really mean "good" or do you mean "optimal"? I can think of a few "good" approaches :) — dvogel
Hamish: Subgraphs cannot contain more nodes than specified (must be equally sized, possibly +-1 if node count is uneven). Jacob: It's a problem of merging big datasets from multiple servers in parallel and without running out of diskspace ;-) dvogel: Greedy construction one node at a time while keeping 50 best results seems to work well enough in practice, I was just wondering if it was maybe some well-known problem with a better algorithm. — taw

Aaron Aaron · Accepted Answer · 2010-07-16T03:25:32

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

Is there a good algorithm for this graph problem?

1 Answers