[C Program]

5 Reductions and Boolean Satisfiability II (Hitting Set)) In this question, we consider the litting Set problem defined as follows: Given a collection of subsets of a finite set S, and a positive integer KC, find a subset of S with at most K elements that contains at least one element from each element C' of C. We call the set that contains at least one element from each C' in C a hitting set. For instance, if S = {1,2,3,4,5,6,7,8,9} and C = {{1,2,4,8}, {2, 3, 5, 7}, {4,8,9}, {1,3,9}, {5}} then there is a hitting set with 3 elements (K = 3), for instance (2,5,9}, but there is no hitting set with only 2 elements (K = 2). 1. [5 points) Show how to reduce a arbitrary instance of the Titling Set problem into an instance of Boolean Satisfiability (SAT). Ilint: you will want to introduce K variables for each element of S. 2. [1 point] Write the collection of clauses you would get for the instance S = {1,2,3,4}, C={{1}, {2, 3}, {3,4}} and K = 3. 3. [2 points What is the length of the instance of SAT that your algorithm generates, as a function of the number n of elements of S, the total size of the elements of C (m= Eceo C']), and the integer K? 4. [4 points] Explain briefly why, if the input graph has a hitting set with at most K elements, then there is a way to assign values to the variables in the instance of SAT that makes every clause TRUE. 5. [4 points) 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 set S and the collection of subsets in the instance of Ilitting Set must have a hitting set with at most K elements. Show how you would determine which elements of S are in that hitting set