My professor gave the reduction of Independent Set (IS) $\leq_p$ SAT where SAT is the set of all satisfiable propositional formulas in conjunctive normal form, and IS the set of all pairs (G,k) where G is an undirected graph with an independent set of size k, given as as an exercise and I'm a little confused as to what I am supposed to do to get this reduction.

I know that we have to define a function $f$ that'll map IS to SAT but I'm not entirely sure on how to approach this question.

Tips on intuition or how to approach this question are greatly appreciated! Thanks in advance!

  • $\begingroup$ What about using the proof of Cook-Levin theorem? $\endgroup$ – xskxzr Mar 15 '18 at 3:19
  • $\begingroup$ In addition, it seems the title should be "reduce IS to SAT". $\endgroup$ – xskxzr Mar 15 '18 at 3:22
  • $\begingroup$ Right thanks! Ill look into the Cook-Levin Theorem $\endgroup$ – Gbravo Mar 15 '18 at 3:33
  • $\begingroup$ Cook-Levin solves the problem but that's like using a sledgehammer to crack a nut. It's almost certainly not what your professor had in mind. $\endgroup$ – Sebastian Oberhoff Mar 15 '18 at 3:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.