5. Maximum Independent Set on Trees
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 children 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 grandchildren 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),\ w(v)+\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.