CSE 421 Assignment #7
Winter 2003

Due: Wednesday, March 12, 2003.

Reading Assignment: Read Chapter 7 of Kleinberg and Tardos.

Problems: For all problems on this homework prove that your algorithm is correct and analyze its worst-case running time.

1. Kleinberg and Tardos, Section 6.11, Problem 11, page 235.

2. Kleinberg and Tardos, Section 6.11, Problem 13, page 235.

3. Kleinberg and Tardos, Section 7.8, Problem 4, page 286.

4. The Dominating Set Problem asks given an undirected graph G=(V,E) and an integer k whether or not there is a subset D of V of size at most k such that every vertex v in G is either in D or adjacent to a vertex in D. Prove that the Dominating Set is NP-complete.
   HINT: Use a reduction from Vertex Cover that replaces edges by triangles.

5. Extra credit: Kleinberg and Tardos, Section 6.11, Problem 9, page 234.

6. Extra credit: Feedback on Chapters 1 to 7 of Kleinberg and Tardos. This should be sent in e-mail to the address cse421-textbook@cs. Your message should contain your name prominently displayed at the start as well as the number of the chapter for which you are providing comments. If you have more than one comment, your comments should be laid out in some form of numbered or bulleted list.