3502 Fall 2017
due 12/6/17 in class
Solutions will be discussed in class on Wednesday 12/6 (to help review for the final exam on Monday 12/11).
Problem 1. Membership in NP
(a) Show that MAX-CUT is in NP (it is defined in Exercise 7.27).
(b) Show that 3-COLOR is in NP (it is defined in Exercise 7.29).
Note: both of these problems are actually NP-complete.
Problem 2. Reductions to YES/NO problems
(a) The CLIQUE problem takes k, the size of the clique, as one of the arguments. As we know, this problem is in NP, and no polynomial-time solution is known.
Show that, if CLIQUE was in P (that is, if NP = P), then there would be a polynomial-time algorithm FIND-LARGEST-CLIQUE that, given a graph (and nothing else), finds the largest clique in it (or one of them, if there are multiple). Note that FIND-CLIQUE is not a YES/NO algorithm, since it returns the actual clique.
Hint: use CLIQUE as a boolean subroutine for FIND-CLIQUE .
(b) Show that, if HAMPATH was in P (that is, if NP = P), then there exists a polynomial-time algorithm FIND-HAMPATH that actually finds the Hamiltonian path from s to t (or one of them, if there is more than one). Note that FIND-HAMPATH is not a YES/NO algorithm, since it returns the actual Hamiltonian path.
Hint: use HAMPATH as a boolean subroutine for FIND-HAMPATH
Problem 3. Proving NP-completeness of a language
Exercise 7.30 (SET-SPLITTING)
Hint: think of red and blue as truth values.