5
$\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.

Improve this question
$\endgroup$
7
  • $\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
    Commented Jun 14, 2013 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
    Commented Jun 14, 2013 at 5:27
  • 1
    $\begingroup$ This is a variant of the Correlation Clustering problem. The problem is NP-hard. $\endgroup$
    – Yury
    Commented Jun 14, 2013 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
    Commented Jun 14, 2013 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
    Commented Jun 14, 2013 at 19:48

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ I need this as a hobbyist... I can't pay 40 euro for those publications without even knowing if it will help me :(. Isn't there a publication somewhere that shows a good algorithm that is free? $\endgroup$
    – Carlo Wood
    Commented Oct 24, 2022 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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