CSDS 455: Applied Graph Theory
Homework 20
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|).
