2
$\begingroup$

Is there a common name for this problem:

Let G=(V, E) be an undirected graph. Partition V into sets $S_1$, $S_2$, ..., $S_k$, such that (the number of edges between sets) + (the number of "non"-edges within sets) is minimized.

To be clear: define "extra edges" to be the set of edges with endpoints in different sets; define "missing edges" to be the set of edges in the complement of G with endpoints in the same set. The goal is to find a partition that minimizes the sum of "extra edges" and "missing edges".

(The sets need not be of similar size.)

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

This is the Min-Disagreements version of the correlation clustering problem (on complete graphs), defined by Bansal, Blum, and Chawla (full version). They give a (huge) constant factor approximation for the problem and prove it's NP-hard. Charikar, Guruswami, and Wirth show the problem is APX-hard, and improve the approximation factor to 4 via region growing. There is a beautiful and simple combinatorial algorithm (a variant of QuickSort), due to Ailon, Charikar, and Newman, that gives a factor 3 approximation. I believe the current best known approximation ratio is due to Chawla, Makarychev, Schramm, and Yaroslavtsev, and is around 2.06.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ It's worth noting that the value of $k$ (the number of clusters) is not part of the input for correlation clustering; the algorithm is free to choose whatever number of clusters it thinks is best. $\endgroup$
    – Andrew Morgan
    Commented Jun 4, 2016 at 7:34
  • $\begingroup$ @AndrewMorgan that's a good point $\endgroup$
    – Sasho Nikolov
    Commented Jun 4, 2016 at 14:57
  • $\begingroup$ Are there any implementations of the approximation algorithms available (perhaps either Demaine and Immorlica or Emanuel and Fiat)? $\endgroup$
    – Zack
    Commented Jun 7, 2016 at 19:46
  • $\begingroup$ I know the region growing algorithm was implemented in the context of modularity maximization here. It's also not a difficult algorithm to code up, as long as you get yourself an LP solver, although the LP is unfortunately quite big. The quick-sort based algorithm is simpler, and doesn't require solving an LP. $\endgroup$
    – Sasho Nikolov
    Commented Jun 8, 2016 at 22:53
2
$\begingroup$

In the parameterized complexity community, it is called cluster editing. See e.g. "Cluster graph modification problems", Ron Shamir, Roded Sharan and Dekel Tsur, Discrete Applied Mathematics 2004, doi:10.1016/j.dam.2004.01.007, "Efficient Parameterized Preprocessing for Cluster Editing", Michael Fellows, Michael Langston, Frances Rosamond, and Peter Shaw, FCT 2007, doi:10.1007/978-3-540-74240-1_27, and this related question.

Improve this answer
$\endgroup$

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.