Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

5. Maximum Independent Set on Trees

  • Advanced Algorithms
    • Flows
    • Intractability
    • Approximation Algorithms
    • Randomized Algorithms
    • Greedy Algorithms
      • 1. Storing Files on a Tape
      • 2. A Scheduling Problem
      • 3. Stable Matchings
    • Matroids
      • 1. The Motivation
      • 2. The Definition
      • 3. Greedy Works!
      • 4. Scheduling with Deadlines
    • Dynamic Programming
      • 1. Longest Increasing Subsequence
      • 2. Subset Sum
      • 3. Set Cover
      • 4. Optimal BSTs
      • 5. Maximum Independent Set on Trees

On this page

  • The Problem
  • The Solution

5. Maximum Independent Set on Trees

algonotes
lecturenotes
Published

May 16, 2023

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.


© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×