Tell me more ×
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.
up vote 1 down vote favorite

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
1  
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

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

1 Answer

up vote 1 down vote

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

 
discard

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.