Maximum Cut Optimisation Problem

Definition

Maximum Cut Optimisation Problem

Instance: A finite simple undirected graph $G=(V,E)$.

Feasible solutions: Bipartitions $(A,B)$ with $A\cup B=V$ and $A\cap B=\varnothing$; either part may be empty.

Objective: Maximise the number of crossing edges:

\operatorname{CUT}(A,B)=\{\{u,v\}\in E:u\in A,\ v\in B\}.$$ Each edge has unit value. An edge contributes precisely when its endpoints lie on opposite sides.