How to show that Max-cut$_{dec}$ is NP-complete using Mon-NAE-3SAT ?

Mon-NAE-3SAT definition :

An instance is a m clauses of three positive literals (no complemented variable) $x \vee y \vee z$ The question: is whether there is a Boolean assignment that ensures that each clause contains at least one variable

Max-cut$_{dec}$ definition :

Let $G = (V,E)$ be an undirected graph. A cut (or cut) is a partition of $V$ into two subsets $V_1, V_2$. The size of a cut, note $c(V_1,V_2)$, is the number of edges $(u,v)$ of $E$ such that $u \in V_1$ and $v \in V_2$ or, conversely, $u \in V_2$ and $v \in V_1$.

The Max-cut optimization problem is finding the largest cut. In its decision version, Max-cut$_{dec}$, each instance also includes a $k$ size objective and you have to decide if it exists a cut of $k$ size or more.

actually I'm stuck on how to show :

  • that if $x, y, z$ are on the same side of the cut then the gadget contains at most 4 edges counted in the cut.
  • that if the three points $x,y,z$ are not all on the same side of the cut, then we can place points $a,b,c$ in $V_1$ or $V_2$ so that the gadget contains 5 edges counted in the cut.

I put the gadget below which represents an $x \vee y \vee z$ clause.

enter image description here



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.