Independent set (Fundamental algorithms, Spring 2023, Lecture 13)
Kent Quanrud · 75:51
Independent set on general undirected graphs is NP-hard (a polynomial algorithm would also solve 3-SAT), but the same problem becomes polynomial once the graph has enough structure: O(n log n) dynamic programming on i...