Dynamic Programming on Trees

Using dynamic programming to solve the largest independent set problem in trees

So far, all of our dynamic programming examples use multidimensional arrays to store the results of recursive subproblems. However, as the next example shows, this is not always the most appropriate data structure to use.

An independent set in a graph is a subset of the vertices with no edges between them. Finding the largest independent set in an arbitrary graph is extremely hard; this is one of the canonical NP-hard problems, but we won’t be studying it in this course. But in some special classes of graphs, we can find the largest independent sets quickly. In particular, when the input graph is a tree with $n$ vertices, we can actually compute the largest independent set in $O(n)$ time.

Suppose we are given a tree $T$. Without loss of generality, suppose $T$ is a rooted tree; that is, there is a special node in $T$ called the root, and all edges are implicitly directed away from this vertex. (If $T$ is an unrooted tree—a connected acyclic undirected graph—we can choose an arbitrary vertex as the root.) We call vertex $w$ a descendant of vertex $v$ if the unique path from $w$ to the root includes $v$; equivalently, the descendants of $v$ are $v$ itself and the descendants of the children of $v$. The subtree rooted at $v$ consists of all the descendants of $v$ and the edges between them.

For any node $v$ in $T$, let $MIS(v)$ denote the size of the largest independent set in the subtree rooted at $v$. Any independent set in this subtree that excludes $v$ itself is the union of independent sets in the subtrees rooted at the children of $v$. On the other hand, any independent set that includes $v$ necessarily excludes all of $v$’s children and therefore includes independent sets in the subtrees rooted at $v$’s grandchildren. Thus, the function $MIS$ obeys the following recurrence, where the nonstandard notation $w ↓ v$ means “$w$ is a child of $v$”:

$$MIS(v) = max \begin{Bmatrix} \underset{w\downarrow v}{\sum}MIS(w), 1+ \underset{w\downarrow v}{\sum} \space\underset{x\downarrow w}{\sum} MIS(x) \end{Bmatrix}$$

We need to compute $MIS(r)$, where $r$ is the root of $T$.