2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Albert Hendriks Jun 25 '18 at 10:06
1
$\begingroup$

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.

$\endgroup$

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.