NP Completeness 5 - Independent Set Problem

In this video we introduce the Independent Set problem and prove that it is also NP Complete by reducing 3 SAT to it.

[Bearisgoodboy]

Finding these videos 2 days before final, thank you very much good sir.

[crossfadez]

Amazing explanation. I was really struggling with this because I am self-studying and had no one to help me. Thank you!

[lindsey]

It’s such a clear explanation, thank you so much !

[jeremykong]

thank you for the study video! Pro Painter!

[akshayganji]

In the beginning the problem had 4 vertices in the independent set {v1, v6, v3, v8}. But the reduction using the constructed graph gave a solution with maximum of 3 nodes. How does this work?

[yoonchaena]

Thank you~! Could you share the example answer???

[cortom]

As it is your reduction is wrong, you need to specify that if a literal appears in several clauses you have to add one vertex for each copy.
Then you have to add an edge from each copy of each literal to all copies of its negation. In your example no literal appears twice, hence the problem is easy to miss.
If you don't do that then your proof does not hold because many clauses may be satisfied because of the same literal, thus your satisfying assignment may correspond to a set of less than m vertices

[gladyouseen]

Prof share pdf. Dont be greedy. please share😅