Suppose you know that the CLIQUE problem is NP-hard. Prove that INDEPENDENT SET is NP-hard by providing a Karp reduction F and proving that F is a Karp reduction. Recall that CLIQUE takes as input a pair (G, k) where G is a simple graph and k is a positive integer, and asks whether G has a clique of size k. INDEPENDENT SET has the same input pair, but asks whether G has an independent set of size k. Remember that every Karp reduction must satisfy several properties. For this problem, it means 1. F takes polynomial time to compute (2 points) 2. the size of F(G, k) is polynomial in the size of (G,k)-where the size of (G, k) means the amount of space you need to represent the pair (G, k). For this problem, what's relevant is that the size of the graph G is the total of the number of vertices and number of edges, and k cannot be larger than the number of vertices for the input to be a yes-instance. (2 points) 3. F maps yes-instances to yes-instances (5 points) 4. F maps no-instances to no-instances. (5 points) The last two properties are equivalent to proving that if F(G, k) (H, k'), then G has a clique of size k if and only if H has an independent set of size k Hints: 1. consider the function F that maps pairs (G, k) to (Ge, k), where Ge is the complement of graph G (and recall that the complement of a simple graph is also a simple graph - we don't add in any self-loops). 2. For proving that F maps no-instances to no-instances, it might be easiest to do this by contradiction