# 2-way Graph Partitioning problem

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.