[Solved] CSDS455 Homework 20-dynamic programming algorithm

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 T_k. The algorithm should start at the “leaves” of T_k (the vertices whose neighborhood is a k-clique) and work to the “root” (a K_k clique that is part of the K_k+1 clique in the base case in the recursive definition of T_k). The algorithm should run in time O(k|T_k|).

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(2^k|G|).