4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (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$. $\endgroup$ – usul Jun 14 '13 at 1:30
  • $\begingroup$ "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. $\endgroup$ – gareth Jun 14 '13 at 5:27
  • 1
    $\begingroup$ This is a variant of the Correlation Clustering problem. The problem is NP-hard. $\endgroup$ – Yury Jun 14 '13 at 5:42
  • 1
    $\begingroup$ 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. $\endgroup$ – gareth Jun 14 '13 at 5:53
  • 1
    $\begingroup$ Correlation clustering has been studied in the general weighted case as well. See for example erikdemaine.org/papers/Clustering_TCS/paper.pdf $\endgroup$ – Suresh Venkat Jun 14 '13 at 19:48
3
$\begingroup$

In addition to Correlation Clustering, this is known as Clique Partitioning or Weighted Cluster Editing, see e.g.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.