6.7 Independent sets in trees

6.7 Independent sets in trees

A subset of nodes $S\subset V$ is an independent set of graph $G=(V,E)$ if there are no edges between them. For instance, in Figure 6.10 the nodes 1, 5 form an independent set, but nodes 1, 4, 5 do not, because of the edge between 4 and 5. The largest independent set is 2, 3, 6 .

Figure 6.10 The largest independent set in this graph has size 3.

Like several other problems we have seen in this chapter (knapsack, traveling salesman), finding the largest independent set in a graph is believed to be intractable. However, when the graph happens to be a tree, the problem can be solved in linear time, using dynamic programming. And what are the appropriate subproblems? Already in the chain matrix multiplication problem we noticed that the layered structure of a tree provides a natural definition of a subproblem—as long as one node of the tree has been identified as a root.

So here’s the algorithm: Start by rooting the tree at any node r. Now, each node defines a subtree—the one hanging from it. This immediately suggests subproblems:

$I(u)=sizeoflargestindependentsetofsubtreehangingfromu$.

Our final goal is $I(r)$

Dynamic programming proceeds as always from smaller subproblems to larger ones, that is to say, bottom-up in the rooted tree. Suppose we know the largest independent sets for all subtrees below a certain node $u;$ in other words, suppose we know $I(w)$ for all descendants w of $u.$ How can we compute $I(u)?$ Let’s split the computation into two cases: any independent set either includes u or it doesn’t (Figure 6.11).

I (u) = max {1 + ∑_ text grandchildren w text of u I (w), ∑_ text children w text of u I (w) }.$$I(u)=\max \left\{1+\sum _{\text{grandchildren}w\text{of}u}I(w),\sum _{\text{children}w\text{of}u}I(w)\right\}.$$

If the independent set includes $u,$ then we get one point for it, but we aren’t allowed to include the children of u—therefore we move on to the grandchildren. This is the first case in the formula. On the other hand, if we don’t include u, then we don’t get a point for it, but we can move on to its children.

The number of subproblems is exactly the number of vertices. With a little care, the running time can be made linear, $O(|V|+|E|)$ .

Figure 6.11 I($u$) is the size of the largest independent set of the subtree rooted at u. Two cases: either u is in this independent set, or it isn’t.