How can i show/explain/prove that Max-Cut is in NP? "For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the Max-Cut Problem."
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
The decision version of MAX-CUT is as follows:
Given a graph $G$ and an integer $k$, is there a cut in $G$ containing at least $k$ edges?
This version is clearly in NP.