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.)

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

$\endgroup$
  • 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 Jun 4 '16 at 7:34
  • $\begingroup$ @AndrewMorgan that's a good point $\endgroup$ – Sasho Nikolov Jun 4 '16 at 14:57
  • $\begingroup$ Are there any implementations of the approximation algorithms available (perhaps either Demaine and Immorlica or Emanuel and Fiat)? $\endgroup$ – Zack Jun 7 '16 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 Jun 8 '16 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.

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