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."


  • $\begingroup$ The Wikipedia article you are citing tells you why it is easy to see that the decision version of the problem is in NP. Quote : "It is easy to see that the problem is in NP: a yes answer is easy to prove by presenting a large enough cut." $\endgroup$
    – Tassle
    Aug 4 '19 at 20:51
  • $\begingroup$ The NP version is, given a graph and an integer $k$, to determine whether the graph has a cut containing at least $k$ edges. $\endgroup$ Aug 4 '19 at 21:12
  • $\begingroup$ @Tassle - you are not helping. clearly i saw this cite in wikipedia. the question is why if i want to prove that max-cut is in NP is need to talk about the this decision problem. $\endgroup$
    – user108220
    Aug 5 '19 at 7:23

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.

  • $\begingroup$ What you are talking about the decision version? what is the formal way to do it? $\endgroup$
    – user108220
    Aug 5 '19 at 7:21
  • $\begingroup$ MAX-CUT can be considered both as a decision problem (as in my answer) and as an optimization problem (given a graph, find a cut maximizing the number of edges cut). The version you quote in your OP is unfamiliar to me. $\endgroup$ Aug 5 '19 at 7:22
  • $\begingroup$ NP is a category of decision problems. Only decision problems can be in NP. $\endgroup$ Aug 5 '19 at 7:23
  • $\begingroup$ The version im talking is this one (as you wrote): "given a graph, find a cut maximizing the number of edges cut" $\endgroup$
    – user108220
    Aug 5 '19 at 7:25
  • $\begingroup$ This is not a decision problem, so it cannot be in NP. Only decision problems can be in NP. A decision problem is one in which the answer is either Yes or No. $\endgroup$ Aug 5 '19 at 7:25

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.