9.1 Independent sets and vertex covers

Question 1

What is an independent set

Answer 1

Question 2

What is the decision problem for finding a maximum independent set

Answer 2

Question 3

How to reduce 3-SAT to finding a max independent set, and hence proving that a max independent set is NP-hard (it is also complete)

Answer 3

• Each variable is modeled by a gadget which represents it being T/F
• Each clause is modeled by a triangle gadget
• Linking variable to clause gadgets models assignment for max set

Question 4

Reduce finding a maximum independent set (decision version) to finding a mininum vertex cover (decision version)

Answer 4

Question 5

Since finding a vertex cover is NP-complete, what does that say about Integer Linear Programming

Answer 5

• It is NP-hard