CSE 3502 Fall 2017
Homework 10
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.