lazycamper
lazycamper

Reputation: 117

Reduce SAT <=p Independent Set

I am a bit confused. I know how to reduce 3-SAT to IS. An example of transforming 3-SAT to IS graph would be create a graph representing each clause of the 3-SAT and then joining the x and !x and then submitting it to IS. How would we apply this to a more generic SAT <=p IS reduction, without reducing SAT to 3-SAT? To me it seems like it would be the same way, but I have a feeling that is not the case and I am missing something. An instance of SAT:

x1 ∧ (x2 ∨ ̄x1) ∧ (x3 ∨ x4 ∨ ̄x2)

Would we transform this in the same way, and is there a generic sequence of steps to use for all instances of SAT? How would I prove it?

Upvotes: 1

Views: 665

Answers (0)

Related Questions