CSE 417 Homework 6, Winter 2011

Problems

1. Take the following instance A of 3-SAT and reduce it to an instance B of VERTEX-COVER

   (x1 v x2 v x3) ^ (x1' v x3 v x4) ^ (x1' v x3' v x4') ^ (x2' v x3' v x4)
   

   a. Create B. (Construct the graph and specify the appropriate value of k.)

   b. Identify a vertex cover C of size at most k for B.

   c. From C, determine a satisfying assignment T for A.


 

2. (20 points) The 2D-POINT-COVERING problem is this: Given a set of N points in the 2D cartesian plane, and a non-negative integer k, is it possible to cover the points with k or fewer tiles. Each tile is square (1 by 1) and can be positioned anywhere in the plane, provided its sides remain parallel to the x or y axes. Prove that the 2D-POINT-COVERING problem is in NP.

 

3. (20 points) Do exercise 1 on p. 505.

 

4. (40 points) Do exercise 12 on p. 510.

   (a) For 15 points, show that EVASIVE-PATH is in NP.

   (b) For 25 points, provide a reduction of any NP-complete problem to EVASIVE-PATH.