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.