Tutorial questions for November 20th, 21st and 26th

In these problems, we revisit the following problem that already appeared on a previous tutorial, on a tutorial quiz, and on the assignment:

Vertex cover: Given a graph G = (V, E) and an integer K, we want to find a vertex cover with K vertices in G. That is, we want a subset W of V such that |W| = K, and the property that every edge in E has at least one endpoint in W.

1. Prove that the vertex cover problem belongs to NP.
2. In order to prove that the vertex cover problem is NP-complete, we need to either
   • Reduce the vertex cover problem to a known NP-complete problem (say, 3SAT), or
   • Reduce a known NP-complete problem (say, 3SAT) to the vertex cover problem
   Which one is it, and why?
3. For the remainder of this tutorial, we will be reducing 3SAT to vertex cover (whether or not it is the correct answer to question 2). Given an instance of 3SAT with n variables X₁, X₂, ..., X_n, and m clauses C₁, C₂, ..., C_m, we construct a graph as follows:
   • We generate 2n nodes which we will call X₁, X₁, X₂, X₂, ..., X_n, X_n and n edges { X₁, X₁ }, { X₂, X₂ }, { X_n, X_n }.
   • We generate 3m nodes which we call Y_1,1, Y_1,2, Y_1,3, Y_2,1, Y_2,2, Y_2,3, ..., Y_m,1, Y_m,2, Y_m,3 and 3m edges { Y_1,1, Y_1,2 }, { Y_1,1, Y_1,3 }, { Y_1,2, Y_1,3 }, { Y_2,1, Y_2,2 }, { Y_2,1, Y_2,3 }, { Y_2,2, Y_2,3 }, ..., { Y_m,1, Y_m,2 }, { Y_m,1, Y_m,3 }, { Y_m,2, Y_m,3 }.
   • Finally, for each literal X_i (say) that appears at position j in clause C_k, we add the edge { Y_m,j, X_i }.

   Draw the graph constructed by the reduction for the following instance of 3SAT: (X₁ v X₂ v v X₃) ^ (X₁ v X₂ v X₃) ^ (X₂ v X₃ v X₄) ^ (X₁ v X₃ v X₄).

4. Choose a value of K with the property that the instance of 3SAT is satisfiable if and only if the graph constructed by the reduction has a vertex cover with at most K elements.
5. Prove that if the instance of 3SAT is satisfiable, then the graph constructed by the reduction has a vertex cover with at most K elements.
6. Prove that if the graph constructed by the reduction has a vertex cover with at most K elements, then the instance of 3SAT is satisfiable.