I am trying to reduce NOT-ALL-EQUAL SAT to MAX-CUT with weighted edges.

I know that if there are weights to the edges, then I can reduce NOT-ALL-EQUAL SAT to MAX CUT by have a $G$ with $2n$ nodes ($x_i$ and $\bar{x}_i$) and edges between the nodes based on each clause. And, adding edges between $x_i$ and $\bar{x}_i$, so on. But, I am not sure how to assign weights if I have to reduce a NOT-ALL-EQUAL SAT to weighted MAX CUT.

How should I go about this problem?


migrated from cstheory.stackexchange.com Dec 2 '12 at 6:20

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ btw why can't you reduce unweighted MAX CUT to weighted MAX CUT ? $\endgroup$ – Suresh Dec 2 '12 at 3:17
  • $\begingroup$ I don't remember well the reduction from NAE-SAT to unweighted MAX CUT, but why can't you use the same reduction from NAE SAT to weighted MAX-CUT with all edges having weight 1 ? $\endgroup$ – Vor Dec 2 '12 at 15:57
  • $\begingroup$ @Suresh, hmmm how would I assign weights if I have to reduce unweighted MAX CUT to weighted MAX CUT? $\endgroup$ – hashpling Dec 2 '12 at 20:28
  • $\begingroup$ well all weights are 1, as @Vor says $\endgroup$ – Suresh Dec 2 '12 at 21:10

NAE-SAT is clearly in NP, while MAX-CUT is NP-complete. So by the definition of NP-complete, there is some reduction from NAE-SAT to MAX-CUT.


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.