# CSE 417 Homework 6, Winter 2011

Do this assignment independently. Submit your answers on paper in class on Friday, March 11.

### 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.
3. (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.

4.
5. (20 points) Do exercise 1 on p. 505.

6.
7. (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.

Last updated: March 2, 2011.