Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

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.

btw why can't you reduce unweighted MAX CUT to weighted MAX CUT ? –  Suresh Dec 2 '12 at 3:17
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 ? –  Vor Dec 2 '12 at 15:57
@Suresh, hmmm how would I assign weights if I have to reduce unweighted MAX CUT to weighted MAX CUT? –  Pavanred Dec 2 '12 at 20:28
well all weights are 1, as @Vor says –  Suresh Dec 2 '12 at 21:10

1 Answer 1

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.