Skip to main content
edited tags
Link
Kaveh
  • 21.8k
  • 8
  • 84
  • 185
Source Link
Aaron Roth
  • 9.9k
  • 1
  • 44
  • 68

A Multi-cut Problem

I'm looking for a name or any references to this problem.

Given a weighted graph $G = (V, E, w)$ find a partition of the vertices into up to $n = |V|$ sets $S_1,\ldots,S_n$ so as to maximize the value of the cut edges: $$c(S_1,\ldots,S_n) = \sum_{i \ne j}\left(\sum_{(u,v)\in E : u \in S_i, v \in S_j}w(u,v)\right)$$ Note that some of the sets $S_i$ can be empty. So the problem is essentially max k-cut, except $k$ is not part of the input: the algorithm can choose any $k$ it likes so as to maximize the value of the cut edges. Obviously, the problem is trivial if edge weights are non-negative: simply place every vertex alone in its own set, and you cut all of the edges. But, to make things interesting, negative weight edges are allowed.

Is this a studied problem? References to algorithmic or hardness results would be appreciated!