# 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!

• To get more intuition about the problem, what do you know about simple special cases? For example, what if the weights are just $+1$ or $-1$? What if $G$ is a complete graph and the weights are $\pm 1$? – Jukka Suomela Dec 9 '10 at 23:32

The problem is a variant of Correlation Clustering (CC) Bansal, N., Blum, A. and Chawla, S. (2004). "Correlation Clustering". Machine Learning Journal (Special Issue on Theoritical Advances in Data Clustering,. pp. 86–113, doi:10.1023/B:MACH.0000033116.57574.95.

The original CC formulation is on a complete graph $G$ and for each edge $(v,w)$ we have two weights: $a(v,w)$ and $b(v,w)$. Given a partition $P$, let $c_P(v,w)$ be equal to $a(v,w)$ if $v$ and $w$ are in the same cluster of $P$ and $b(v,w)$ otherwise. Then the value of a partition $P$ of $V$ is $\sum_{v,w} c(v,w)$.

Your problem is equivalent to $a(v,w)=0$ for all v,w and allowing negative $b(v,w)$ (the original paper allowed only +1,-1 weights). The paper Erik D. Demaine, Dotan Emanuel, Amos Fiat, Nicole Immorlica: Correlation clustering in general weighted graphs. Theor. Comput. Sci. 361(2-3): 172-187 (2006) http://dx.doi.org/10.1016/j.tcs.2006.05.008 gives a $O(\log n)$-approximation algorithm for general (i.e. not complete) graphs. I believe it can be extended also to your problem, and I would not rule out a constant-factor approximation.

The PTASs described are based on the smooth polynomial programming technique: in the most general case I don't think your problem would satisfy the requirement of the technique.

I don't know of any references, but I can show that it's NP-complete, via a reduction from graph coloring.

Given a graph G and a number k of colors with which to color G, make a new graph G' that consists of G together with k new vertices, such that each new vertex is connected to every vertex in G. Assign weight +kn to each edge of G, weight +kn to each edge connecting two of the k new vertices, and weight -1 to each of the edges connecting the k new vertices to G.

Then, if G can be k-colored, the coloring (together with a partition that assigns each of the new vertices to one of the color classes) achieves total weight kn(m + k(k-1)/2) - (k-1)n.

In the other direction, if you have a partition that achieves this total weight, then it must cut all of the edges of G, and all of the edges between pairs of new vertices. Cutting all of the edges of G defines a coloring of G, and cutting edges between pairs of new vertices implies that each vertex of G can be adjacent to at most one of the k new vertices. Therefore, in order to get the optimal -(k-1)n term in the weight, each vertex of G must be adjacent to exactly one of the new vertices, and therefore there can only be k color classes in the coloring defined by the partition.

That is, partitions with the given weight bound are in 1-1 correspondence with k-colorings of G, so this defines a reduction from coloring to your partition problem.

Let me supplement David’s nice NP-completeness proof by adding a reference to the special case asked by Jukka in a comment on the question. If the graph is the complete graph and the edge weights are restricted to ±1, the problem is equivalent to the NP-complete problem known as Cluster Editing.

Cluster Editing is the following problem introduced by Shamir, Sharan and Tsur [SST04]. Here, a cluster graph is a graph which is a union of vertex-disjoint cliques and an edit is the addition or the removal of one edge.

Cluster Editing
Instance: A graph G=(V, E) and an integer k∈ℕ.
Question: Is it possible to turn G into a cluster graph by at most k edits?

Cluster Editing is NP-complete [SST04].

To see Cluster Editing is equivalent to the aforementioned special case of the current problem, let G=(V, E) be a graph. Let n=|V| and consider G as a subgraph of the complete graph Kn. In Kn, give the weight −1 to the edges in G and the weight +1 to the edges not in G. Then G can be turned into a cluster graph by at most k edits if and only if there exists a partition (S1, …, Sn) such that c(S1, …, Sn) ≥ $\binom{n}{2}$−|E|−k for this weighted complete graph Kn.

[SST04] Ron Shamir, Roded Sharan and Dekel Tsur. Cluster graph modification problems. Discrete Applied Mathematics, 144(1–2):173–182, Nov. 2004. http://dx.doi.org/10.1016/j.dam.2004.01.007