Exact 'Fast' Algorithm for the Maximum Independent Set Problem

Here we give a "fast" algorithm for solving the maximum independent set problem for an arbitrary graph, which is NP-complete in this general case. The key to getting a much faster algorithm is to break the graph up into "classes" of vertices based on their degree, and recurse appropriately on each.

Timeline:
0:00 - Intro + Example
2:07 - Brute Force Algorithm
4:00 - Vertices of Degree 0 or 1
10:10 - Vertices of Degree at least 3
13:40 - Vertices of Degree 2
17:35 - Final Runtime

▶SEND ME THEORY QUESTIONS◀

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

[EasyTheory]

Thanks to Micah Wood (Platinum), and Josh Hibschman, Timmy Gy, Patrik Keinonen, and Travis Schnider (Silver) for helping support this video. If you want to contribute, links are in the video description.

[dominiorrr]

Very good explanation, really helped me with my homework. Thanks.

[yijunyin]

Thanks for your explanation. I implement the code based on your algorithm. it works

[basilbeirouti]

The argument around 6:00 that leads to the "without loss of generality" remark is quite handwavey and I didn't understand it. Besides that the whole video is very well explained

[MayankGoel]

In case of degree of a node being 0 or 1, shouldn't we have a case where the node is not included