For this assignment, lookup how dynamic programming algorithms work.
Recall the maximum independent set problem: Given a graph G find the largest independent set of vertices of G. An independent set is an induced subgraph that has no edges.
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|).
