A Multi-cut Problem

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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 K_n. In K_n, 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 (S₁, …, S_n) such that c(S₁, …, S_n) ≥ $\binom{n}{2}$−|E|−k for this weighted complete graph K_n.

[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

Answer 4

To add to the answer of Gianluca Della Vedova, this problem is also known under different names as:

• Clique partitioning (Grötschel and Wakabayashi, 1989): In this problem the objective is to partition the nodes of a complete graph such that the sum of the weights of the edges within the sets of the partition is maximized. As this problem is formulated for complete graphs, each node set induces a clique of the graph and hence the name clique partitioning. This problem is equivalent to the problem of the question because maximizing the weight of the edges within clusters is equivalent to maximizing the edges between clusters after flipping the sign of the edge weights. The fact that this problem is formulated for complete graphs only is no restriction, as any instance for a non-complete graph can be converted to an instance of a complete graph by adding edges with weight 0.

• Edge-sum coalition structure generation (Voice et al., 2012, Bachrach et al., 2013): This problem is basically the same as clique partitioning. The objective is again to maximize the sum of the edges within clusters. This problem is discussed from a game theoretic perspective: The nodes of the graph are called agents and the clusters are coalitions of agents. An edge between two agents indicates how well these agents work together. The objective is to find a coalition structure, i.e. a partition of agents into coalitions, that maximizes productivity.

• Multicut (Deza et al., 1992): This is exactly the problem described in the question. This name is unfortunate in that is causes confusion with multi-terminal cut or multiway cut problems. However, in the last decade this term is frequently by the computer vision community.

The problems mentioned above and the correlation clustering problem mentioned in the answer of Gianluca Della Vedova are all equivalent in the sense that they share the same set of optimal solutions. However, these problems differ greatly when it comes to hardness of approximation. For instance, for maximizing agreement in the correlation clustering problem there exists a trivial 2-approximation algorithm and even better approximation algorithms are known. In contrast to this, it is NP-hard to approximate the clique partitioning problem within a factor of $n^{1-\epsilon}$ for all $\epsilon > 0$. For the variant of the problem in the question, i.e. the multicut problem, very little is known about its hardness of approximation. The only result I am aware of is that approximating multicut is at least as hard as maximizing agreement in correlation clustering (Andres et al., 2023) which is APX-hard.