<p>This is the Min-Disagreements version of the correlation clustering problem (on complete graphs), defined by <a href="http://www.cs.cmu.edu/~avrim/Papers/clustering.ps" rel="nofollow">Bansal, Blum, and Chawla</a> (<a href="http://link.springer.com/article/10.1023/B:MACH.0000033116.57574.95" rel="nofollow">full version</a>). They give a (huge) constant factor approximation for the problem and prove it's NP-hard. <a href="https://courses.cs.washington.edu/courses/cse522/05au/charikarcorrelation.pdf" rel="nofollow">Charikar, Guruswami, and Wirth</a> 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 <a href="http://dimacs.rutgers.edu/~alantha/papers2/aggregating_journal.pdf" rel="nofollow">Ailon, Charikar, and Newman</a>, that gives a factor 3 approximation. I believe the current best known approximation ratio is due to <a href="http://arxiv.org/pdf/1412.0681v3.pdf" rel="nofollow">Chawla, Makarychev, Schramm, and Yaroslavtsev</a>, and is around 2.06.</p>

CC BY-SA 3.0
2016-06-04T07:34:08.307Z
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.
Andrew Morgan
CC BY-SA 3.0
2016-06-04T14:57:34.557Z
@AndrewMorgan that's a good point
Sasho Nikolov
CC BY-SA 3.0
2016-06-07T19:46:40.107Z
Are there any implementations of the approximation algorithms available (perhaps either Demaine and Immorlica or Emanuel and Fiat)?
Zack
CC BY-SA 3.0
2016-06-08T22:53:09.497Z
I know the region growing algorithm was implemented in the context of modularity maximization [here](http://www-bcf.usc.edu/~dkempe/publications/clustering.zip). 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.
Sasho Nikolov
CC BY-SA 3.0
2016-06-04T03:38:17.007Z
2016-06-04T03:38:17.007Z
Sasho Nikolov
<p>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, <a href="http://dx.doi.org/10.1016/j.dam.2004.01.007" rel="nofollow noreferrer">doi:10.1016/j.dam.2004.01.007</a>, "Efficient Parameterized Preprocessing for Cluster Editing", Michael Fellows, Michael Langston, Frances Rosamond, and Peter Shaw, FCT 2007, <a href="http://doi.org/10.1007/978-3-540-74240-1_27" rel="nofollow noreferrer">doi:10.1007/978-3-540-74240-1_27</a>, and <a href="https://cstheory.stackexchange.com/questions/3690/a-multi-cut-problem/3698#3698">this related question</a>.</p>

CC BY-SA 3.0
2016-06-03T22:15:28.430Z
2016-06-03T22:15:28.430Z
2017-04-13T12:32:28.743Z
David Eppstein
<p>Is there a common name for this problem:</p>

<p>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.</p>

<p>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".</p>

<p>(The sets need not be of similar size.)</p>

<graph-theory><max-cut><max-flow-min-cut>
Name of graph partition that balances edges between sets with edges remaining within sets
Zack
# Name of graph partition that balances edges between sets with edges remaining within sets

(Asked by: username_0 on 2016-06-03)

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

**Tags:** graph-theory, max-cut, max-flow-min-cut

---

## 2 answers

### Answer by username_1 on 2016-06-04. Score: 3 | Accepted answer

This is the Min-Disagreements version of the correlation clustering problem (on complete graphs), defined by [Bansal, Blum, and Chawla](http://www.cs.cmu.edu/~avrim/Papers/clustering.ps) ([full version](http://link.springer.com/article/10.1023/B:MACH.0000033116.57574.95)). They give a (huge) constant factor approximation for the problem and prove it's NP-hard. [Charikar, Guruswami, and Wirth](https://courses.cs.washington.edu/courses/cse522/05au/charikarcorrelation.pdf) 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](http://dimacs.rutgers.edu/~alantha/papers2/aggregating_journal.pdf), that gives a factor 3 approximation. I believe the current best known approximation ratio is due to [Chawla, Makarychev, Schramm, and Yaroslavtsev](http://arxiv.org/pdf/1412.0681v3.pdf), and is around 2.06.

> **Comments:**
> **username_2**: 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.  
> **username_1**: @AndrewMorgan that's a good point  
> **username_0**: Are there any implementations of the approximation algorithms available (perhaps either Demaine and Immorlica or Emanuel and Fiat)?  
> **username_1**: I know the region growing algorithm was implemented in the context of modularity maximization [here](http://www-bcf.usc.edu/~dkempe/publications/clustering.zip). 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.  

---

### Answer by username_3 on 2016-06-03. Score: 2

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](http://dx.doi.org/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](http://doi.org/10.1007/978-3-540-74240-1_27), and [this related question](https://cstheory.stackexchange.com/questions/3690/a-multi-cut-problem/3698#3698).


---

