# Reduce Max-Cut to Max-2SAT

I would like to find a reduction from Max-Cut to Max-2Sat. Could someone shed light on this problem, preferably spiced with some intuition?

Thanks, Matan.

• Are you sure you didn't intend to ask for the reverse? (historically, Max-2Sat was shown reducible to Max-Cut according to your first Wikipedia link). – Albert Hendriks Jun 25 '18 at 10:06

Given an instance $G = (V,E)$ for Max-Cut, we create an instance of Max-2Sat with one variable $x_v$ per vertex $v \in V$, and two clauses per edge $(v,w) \in E$: $$x_v \lor x_w, \qquad\overline{x_v} \lor \overline{x_w}.$$ Every subset of $V$ corresponds to a truth assignment for the $x_v$ in a natural way. Furthermore, the number of clauses satisfied is exactly $$|E| + |E(V,\overline{V})|.$$ Intuitively, the edge $(v,w)$ is cut iff $(x_v \lor x_w) \land (\overline{x_v} \lor \overline{x_w})$, and this is why this reduction works.