Maximum Independent Sets of Trees

An independent set of a graph is a subset of the graph’s vertices that are not adjacent to each other. A maximum independent set contains the largest possible number of such vertices.

In general, finding maximum independent sets is NP-hard. However, if the graph is a tree, then you can apply dynamic programming to solve the problem in linear time.

There are a lot of ways that you can define what a tree is, and one way is to define it recursively. So, either a tree is empty or it’s made up of a node and a list of subtrees. And the basic idea behind the algorithm here is to find the maximum independent set of the tree by finding the maximum independent sets of all the subtrees. Thus, you can find an optimal solution to the problem by finding optimal solutions to the problem’s subproblems, which means that the problem has optimal substructure. Because the subproblems also overlap, the problem is a prime candidate for dynamic programming.

I put my Python code on my GitHub. Although I prefer bottom-up dynamic programming in general, I took a top-down approach here, because I found it natural to recurse down the tree.

EDIT: I decided to design and implement a bottom-up version of the algorithm, too. In my implementation, a breadth-first traversal of the tree orders the subproblems such that the tree’s nodes are processed in ascending order, from the bottom level of the tree up to the root of the tree. With that ordering of the subproblems, any given subproblem’s subsubproblems will already be solved, saved in the table, and ready for use.

Sources:

Dasgupta, S., C. H. Papadimitriou, and U. V. Vazirani. Algorithms. New York: McGraw-Hill Education, 2006.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s