We have a graph $G=(V,E)$ and we need to divide this graph into two clusters $A$ and $B$. Some pairs of vertices $u$, $v$ should not be in the same cluster, and we define an edge $(u,v) \in E$. The total cost of a solution is the total number of edges with endpoints both in the same cluster. My goal is to find an algorithm that returns the optimal solution that minimizes this total cost. The solution does not have to be balanced in the sense that the clusters should be of the same size.

I was wondering what the general name for this problem is and what a proper algorithm is that can solve this efficiently. By a colleague I was pointed into the direction of using a (nice) tree decomposition.


You're looking for a maximum cut in the graph – maximizing the number of edges between the partitions minimizes the number within them.

Unfortunately, Max Cut is NP-hard on general graphs and also hard to approximate. There's a polynomial-time algorithm on planar graphs, if that's of any use to you.

| cite | improve this answer | |

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.