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|).