3 Reductions and Boolean Satisfiability II (Vertex Cover) In this question, we consider the Vertex Cover problem defined as follows: Given an undirected graph G = (V, E) with vertices V and edges E, and an integer k, find a verter cover of G: a subset V' of V with at most k elements such that every edge in E has at least one endpoint in V'. 1. [5 marks) Show how to reduce a arbitrary instance of Vertex Cover problem into an instance of Boolean Satisfiability (SAT). Hint: you will want to introduce k variables for each vertex of the graph. 2. [1 marks] Write the collection of clauses you would get for the following graph when k= 3: 3. [2 marks] What is the length of the instance of SAT that your algorithm generates, as a function of the number n of vertices, the number m of edges of the input graph G, and the integer k? 4. (4 marks] Explain briefly why, if the input graph has a vertex cover with at most k vertices, then there is a way to assign values to the variables in the instance of SAT that makes every clause TRUE. 5. (4 marks] Explain briefly why, if there is a way to assign values to the variables in the instance of SAT that makes every clause TRUE, then the graph used to generate the instance must have a vertex cover with at most k vertices. Show how you would determine which vertices of G are in that vertex cover. 3 Reductions and Boolean Satisfiability II (Vertex Cover) In this question, we consider the Vertex Cover problem defined as follows: Given an undirected graph G = (V, E) with vertices V and edges E, and an integer k, find a verter cover of G: a subset V' of V with at most k elements such that every edge in E has at least one endpoint in V'. 1. [5 marks) Show how to reduce a arbitrary instance of Vertex Cover problem into an instance of Boolean Satisfiability (SAT). Hint: you will want to introduce k variables for each vertex of the graph. 2. [1 marks] Write the collection of clauses you would get for the following graph when k= 3: 3. [2 marks] What is the length of the instance of SAT that your algorithm generates, as a function of the number n of vertices, the number m of edges of the input graph G, and the integer k? 4. (4 marks] Explain briefly why, if the input graph has a vertex cover with at most k vertices, then there is a way to assign values to the variables in the instance of SAT that makes every clause TRUE. 5. (4 marks] Explain briefly why, if there is a way to assign values to the variables in the instance of SAT that makes every clause TRUE, then the graph used to generate the instance must have a vertex cover with at most k vertices. Show how you would determine which vertices of G are in that vertex cover