one of Karp's 21 NP-complete problems; Karp showed the NP-completeness by a reduction from the partition problem.

The canonical optimization variant of the above decision problem is usually known as the Maximum-Cut Problem or Max-Cut and is defined as:

The optimization variant is known to be NP-Hard.The opposite problem, that of finding a minimum cut