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.