# How to reduce Independent set to SAT?

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!

• What about using the proof of Cook-Levin theorem? – xskxzr Mar 15 '18 at 3:19
• In addition, it seems the title should be "reduce IS to SAT". – xskxzr Mar 15 '18 at 3:22
• Right thanks! Ill look into the Cook-Levin Theorem – Gbravo Mar 15 '18 at 3:33
• 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. – Sebastian Oberhoff Mar 15 '18 at 3:53