CSE 431 Assignment #7
Spring 2003

Due: Wednesday, June 4, 2003.

Read sections 8.1-8.5 of Sipser's text.

Problems

1. Problem 7.22 page 273.

2. Problem 7.23 page 273.

3. For any k, define DEG-k-SPAN-TREE={<G> | G has a spanning tree with maximum degree at most k}.

   1. Show that DEG-2-SPAN-TREE is NP-complete.

   2. Use a reduction from DEG-2-SPAN-TREE to show that DEG-3-SPAN-TREE is also NP-complete.

   3. Generalize part (b) to show that DEG-k-SPAN-TREE is NP-complete for any integer of k>1.

4. Problem 8.4 page 302.

5. DO EITHER: Problem 8.8 page 302 OR Problem 8.10 page 303.

6. Problem 8.9 page 303.

7. (Bonus) Problem 8.16 page 303.