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 (GC, k), where G 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 IMPORTANT: while collaborating is good, writing up the solution together is not consistent with the policy on collaboration. For example, do not write up the solution together, perhaps at a whiteboard, and then copy it down. Your write-ups should not look similar. The structure of the proof and the ideas can be the same, but the text should not look like you both looked at the same write-up and then modified it. The point is to talk together, draw pictures, think about why it works but not share text