Algorithms for NP-Hard Problems (Section 22.4: Independent Set Is NP-Hard)
Tim Roughgarden Lectures · 27:16
This lecture (Algorithms Illuminated, Part 4, §22.4) proves that Independent Set is NP-hard by reducing 3SAT to it: build a graph whose maximum independent set has size equal to the number of clauses if and only if th...