# Partition graph into complete disjoint subgraphs while maximising sum of edge weights

Has this problem been studied?

We start with a complete, simple, undirected graph with edge weights. The problem is to delete edges so as to partition the graph into complete disjoint subgraphs while maximizing the sum of the edge weights over the whole graph (deleted edges not being counted).

There is no constraint on the size or number of subgraphs in the solution.

Note this is interesting only if there are negative edge weights. Otherwise the solution would be to take the whole graph.

Clearly we would like to delete all the negative-weight edges while keeping all positive-weight edges, but the requirement that disjoint subgraphs be complete makes a trade-off between these goals.

I have seen discussion of similar graph partitioning problems but not this exact one. (Eg it is a bit like the maximum clique problem, but here I want to put every node in a disjoint clique, in the optimal way). I am guessing it is NP-complete. I am interested to know where to start looking for efficient heuristics.

• (1) I am not sure what "complete" means here as we can WLOG fill in any graph with edges of weight zero. (2) This should be very related to the min $k$-cut problem in which we want to partition the graph into $k$ components, each connected, so as to minimize the sum of the edge weights crossing the partition boundaries. Notice that we have Total edge weights = edge weights crossing partition + edge weights within each component, so the objective is the same, except in that problem $k$ is given as a parameter and here you pick the best $k$.
– usul
Jun 14, 2013 at 1:30
• "complete" means that within a disjoint subgraph we must keep all edges between all the nodes in that disjoint subgraph. We are not allowed to add new edges or change weights, we must use, or not use, each node in the original (complete) graph. Jun 14, 2013 at 5:27
• This is a variant of the Correlation Clustering problem. The problem is NP-hard.
– Yury
Jun 14, 2013 at 5:42
• Yury - Aha! Thanks for that. Yes, my problem is as described here: en.wikipedia.org/wiki/Correlation_clustering except my weights are any real number, not constrained to {-1,+1}. Think of them as "degree of agreement (disagreement)" between vertices. Jun 14, 2013 at 5:53
• Correlation clustering has been studied in the general weighted case as well. See for example erikdemaine.org/papers/Clustering_TCS/paper.pdf Jun 14, 2013 at 19:48