5. Maximum Independent Set on Trees

Acknowledgements

Some of this material is borrowed from Jeff Erickson’s chapters on Recursion, Backtracking, and Dynamic Programming. The fun factor at a party formulation can be found in an exercise of Erickson as well as these slides by Dàniel Marx. Thanks to Arya for pointing out a correction.

The Problem

You are planning a corporate party. Every employee e has an amount f(e) \geqslant 0 of fun that they will bring to the party if invited. The total fun in the party is the sum of f(e) over all invited employees e. You want your party to be very fun. In fact, as fun as possible. However, it turns out that if you invite a manager and their direct report together, the party will be absolutely no fun, not for anyone. What’s the best you can do?

Concretely, the problem is the following.

• We are given a graph G = (V,E) that is a rooted tree on n vertices with a weight function w: V \longrightarrow \mathbb{N} and root r.
• We want to output the weight of a max-weight independent set in G.

The Solution

What are the fragments (AKA, what do we want to store)?

For v \in V, let T[v] denote the weight of a max-weight independent set in G_v, which is the subtree of G rooted at v.

Are the fragments going to be useful (AKA, where is the final answer)?

Indeed, T[r] is what we want!

Do we have a kickstart (AKA, what are the base cases)?

If v is a leaf node, then T[v] = w(v).

How do the fragments come together (AKA, how do we compute the values that we have agreed to store)?

For the sake of analysis, fix a max-weight independent set S of G_v. We have to wonder: does S contain v?

• If the answer is no, then S can be viewed as a union of optimal solutions in all the subtrees rooted at the chindren of v.
• If the answer is yes, then S can be viewed as a union of optimal solutions in all the subtrees rooted at the grandchindren of v (since the children are now forbidden), and the vertex v itself.

As always, we take the best of both worlds when we pen down our recurrence:

\operatorname{T}(v)=\max \left\{\sum_{w \downarrow v} \operatorname{T}(w), 1+\sum_{w \downarrow v} \sum_{x \downarrow w} \operatorname{T}(x)\right\},

where the notation w \downarrow v means “w is a child of v”.

Can we put the pieces together without getting stuck (AKA, are the dependencies in step #4 acyclic)?

Proceed from the leaves of the tree upwards.