Problem $5.[22$ points$]$ Many optimization problems on trees can be solved efficiently

using dynamic programming. The method works in general as follows. The tree is rooted

at some node and is processed bottom$-$up$,$ from the leaves to the root, to compute the

optimal value, and record sufficient information to recover an optimal solution. At each

node v of the tree, a subproblem is solved for the subtree rooted at the node v$,$ using the

solutions to the subproblems for the subtrees rooted at the children of v $($or sometimes

even lower descendants$).$ The algorithm can be usually written conveniently as a topdown

recursive algorithm.

In this problem you will use this approach to solve the maximum weight independent

set problem for trees. If T is a tree, and S is a subset of nodes of T$,$ we say that S is an

independent set of T if it does not contain any two adjacent nodes. The maximum weight

independent set problem for trees is the following problem: we are given a tree T$,$ where

every node v has a given positive weight w$($v$),$ and the problem is to compute an

independent set S of T with the maximum possible total weight, $()()$

v S

w S w v

$$

$.$ You can

assume that the tree T has been rooted at some node r$,$ and the input includes for every

node v: the parent p$($v$)$ of v$,$ a list C$($v$)$ of the children of v$,$ and the $($positive integer$)$

weight w$($v$)$ of v$.$

$1.$ For each node v$,$ let T$[$v$]$ be the subtree of T rooted at v$,$ let $($v$)=$ max$\{$ w$($S$)|$ S is an

independent set of T$[$v$]\},$ and let $($v$)=$ max$\{$ w$($S$)|$ S is an independent set of T$[$v$]$ and

v$$S$\}.$ Give $($and justify$)$ a recurrence relation that expresses the parameters $($v$),($v$)$ for

v$,$ in terms of the weight w$($v$)$ of v$,$ and the values of the parameters $$ for the children

of v$.$

$2.$ Give a O$($n$)-$time algorithm for the maximum weight independent set problem for

trees, where n is the number of nodes of the input tree. The algorithm should compute not

only the maximum weight, but also an optimal solution itself $($an independent set of

maximum weight$).$

$($Hint: Give first an algorithm that computes the $$values for all the nodes of the tree,

using the recurrence of part $1.$ From the values $($r$),($r$)$ for the root r$,$ you know

whether a maximum weight independent set of T should include the root r or not. Give

now a second algorithm that uses the $$values to compute a maximum weight

independent set of T$.$ It is most convenient to write the algorithms here as top$-$down

recursive algorithms. $)$