36 Max Independent Set problem on Trees

Trees

An undirected graph on $n$ vertices which is connected and has no cycles is called a tree

Any two of the following three properties imply the third one:

• $G$ has $n-1$ edges
• $G$ has no cycles
• $G$ is connected

Max

Given an undirected graph $G=(V,E)$ on $n$ vertices, find a set $X$ of maximum size such that no vertices in $X$ form an edge of $G$.

Obtaining a recurrence

Root the given tree $T$ at an arbitrary vertex, say $r$.
For each vertex $v\in T$, we use the following notation:

• $T(v)$ is the subtree of $T$ which is rooted at $v$
• $\mathrm{OPT}[v]$ is the size of maximum independent set for the tree $T(v)$
• $\mathrm{children}(v)$ is the set of children of $v$
• $\mathrm{grandchildren}(v)$ is the set of grandchildren (children of children) of $v$.

$$\mathrm{OPT}[v]=\max \{\underset{\text{Don’t pick }v}{\underbrace{\sum _{x\in \mathrm{children}(v)}\mathrm{OPT}[x]}};1+\underset{\text{Pick }v\text{ into ind set}}{\underbrace{\sum _{y\in \mathrm{grandchildren}(y)}}}\}$$

Final answer is $\mathrm{OPT}[r]$ where $r$ is the root.

Correctness:

• If $v$ is in the independent set, then none of its children can be in the independent set
• If $v$ is not in the independent set, then (potentially) all of its children can be in the independent set

Running time

• The array $\mathrm{OPT}$ has $O(n)$ entries
• Filling up a new entry in the array needs to look-ip $O(n)$ existing entries from the array, and do $O(n)$ additions & one max operation
  • This needs $O(n)$ time
• Hence, time required to fill up all entries in the array is $O(n^2)$ = ($n$ entries $\times$ $n$ time to complete each entry)
• Can be improved to $O(n)$ running time by a more careful analysis.