Maximum Independent Set in Trees (Linear Time Algorithm)

Here we give a linear time algorithm for the maximum independent set problem for trees. A tree is a graph without cycles, and an independent set is a set of vertices without edges between them. The trick here is that trees don't have cycles, so answering a question about a vertex and its neighbors partitions the rest of the vertices into "clusters" that have no vertices in common. So we can solve the problem independently for each of the neighbors.

▶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.

[vardanverma]

Thanks bro I am a 2nd year CSE student from IIIT Delhi ..this is very logical explanation with dp involved

[yayasssamminna]

This was very helpful, thanks. just a thought : since the sub-trees are disjoint, isn't this rather just a divide and conquer algorithm? Why is it dynamic? There needs to be some Bellman relation that computes the max IS value for a certain node using the value for sub trees more than once, somehow i fail to see it. Thanks for the video.

[davidblakeway]

"..in fact this problem is so important that I deal with it in my research.." 😊

[LRUC]

Isn’t the simple greedy algorithm guaranteed to provide correct results on trees?

Select node with smallest degree (greater than 0), remove connected nodes, repeat until every node is connected.