CSE 421 Assignment #8
Autumn 2007
Due: Wednesday, December 5, 2007.
Reading Assignment: Finish reading Kleinberg and Tardos Chapter 8
Problems:
For all problems on this homework if you are proving NP-completeness, give a
full argument that shows that your reduction is correct and runs efficiently
and make sure to prove that your problem is in NP also. If you are
giving an algorithm, prove that your algorithm is correct
and show that it runs efficiently.
- Kleinberg and Tardos, Chapter 8, Problem 5, pages 506-507.
- Kleinberg and Tardos, Chapter 8, Problem 18, pages 513-514.
- Kleinberg and Tardos, Chapter 8, Problem 20, page 515-516.
(Hint: Use k-coloring)
- Extra credit:
Kleinberg and Tardos, Chapter 8, Problem 10, pages 508-509.
- Extra credit:
Kleinberg and Tardos, Chapter 8, Problem 37, pages 526-527.