Problem 1: Give a dynamic programming algorithm that finds the maximum independent set on a tree T. The algorithm should start at the leaves of the T and work to the root. The algorithm should run in time
O(|T|).
Problem 2: Give a dynamic programming algorithm that finds the maximum independent set on a k-tree Tk. The algorithm should start at the “leaves” of Tk (the vertices whose neighborhood is a k-clique) and work to the “root” (a Kk clique that is part of the Kk+1 clique in the base case in the recursive definition of Tk). The algorithm should run in time O(k|Tk|).
Problem 3: Give a dynamic programming algorithm that finds the maximum independent set on a graph G with treewidth k. The algorithm should start at the leaves of the tree and work to the root. The algorithm should run in time O(2k|G|).
