image University of Washington Computer Science & Engineering
  CSE 421,  Su '07:  Assignment #7, Due: Monday, August 13, 2007
  CSE Home   About Us    Search    Contact Info 

Due Monday, August 13, 4PM. No Late Papers accepted this time.

Problems:

As part of any NP-completeness results, don't forget to prove that your problem is in NP. For the reductions, you may use any of the NP-complete problems given in the text or in lecture. In particular, for these problems, I'd suggest starting with satisfiability, clique, independent set, set cover, or graph coloring. (3-D matching and subset sum are also commonly useful, but don't look so relevant for these problems.)

  1. [10 points] Text, Chapter 8, #4, page 506.

  2. [20 points] Text, Chapter 8, #19, page 514.

      3. CSE logo Computer Science & Engineering
      University of Washington
      Box 352350
      Seattle, WA  98195-2350
      (206) 543-1695 voice, (206) 543-2969 FAX