# Reduction of Max-cut

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.