Independent set
Kent Quanrud · 75:52
Independent set is NP-hard on general graphs because a polynomial solver for it would also solve 3SAT, but the same problem becomes polynomial once the graph is an interval graph or a tree. This lecture walks through...