Recall the Clique problem: given a graph G and a value k, check whether G has a set S of k vertices that's a clique. A clique is a subset of vertices S such that for all u, v € S, uv is an edge of G. The goal of this problem is to establish the NP-hardness of Clique by reducing VertexCover, which is itself an NP-hard problem, to Clique. Recall that a vertex cover is a set of vertices S such that every edge uv has at least one endpoint (u or v) in S, and the VertexCover problem is given a graph H and a value 1, check whether H has a vertex cover of size at most 1. Note that all these problems are already phrased as decision problems, and you only need to show the NP-Hardness of Clique. In other words, we will only solve the reduction part in this problem, and you DO NOT need to show that Clique is in NP. Q4.1 Let S be a subset of vertices in G, and let C be the complement graph of G (where uv is an edge in C if and only if uv is not an edge in G). Prove that for any subset of vertices S, S is a vertex cover in G if and only if V\S is a clique in C. Note: this is an if and only if proof, i.e. you need to show both directions for full credit. Q4.2 Part 4.1 implies the following result (which you may use without proof): G has a vertex cover of size at most k if and only if the complement of G has a clique of size at least n – k. Use this fact to give a reduction from VertexCover to Clique. Your solution should have the following two steps: i) First, show the reduction: specify how the inputs to VertexCover, G and k, can be transformed to a valid input pair, H and I, for Clique. Make sure to explain why this takes polynomial time. ii) Second, show that the answer to Clique (H,1) can be converted to the answer of VertexCover (G, k). One possibility is to explain how a YES answer to Clique (H,l) also mean YES to VertexCover (G, k), AND a NO answer to VertexCover (H, 1) must also mean NO to Clique (G, k). (Hint: The claim we proved in part a) is an if and only if statement.)
Recall the Clique problem: given a graph G and a value k, check whether G has a set S of k vertices that's a clique. A clique is a subset of vertices S such that for all u, v € S, uv is an edge of G. The goal of this problem is to establish the NP-hardness of Clique by reducing VertexCover, which is itself an NP-hard problem, to Clique.
Recall that a vertex cover is a set of vertices S such that every edge uv has at least one endpoint (u or v) in S, and the VertexCover problem is given a graph H and a value 1, check whether H has a vertex cover of size at most 1. Note that all these problems are already phrased as decision problems, and you only need to show the NP-Hardness of Clique. In other words, we will only solve the reduction part in this problem, and you DO NOT need to show that Clique is in NP.
Q4.1
Let S be a subset of vertices in G, and let C be the complement graph of G (where uv is an edge in C if and only if uv is not an edge in G).
Prove that for any subset of vertices S, S is a vertex cover in G if and only if V\S is a clique in C. Note: this is an if and only if proof, i.e. you need to show both directions for full credit.
Q4.2
Part 4.1 implies the following result (which you may use without proof): G has a vertex cover of size at most k if and only if the complement of G has a clique of size at least n – k. Use this fact to give a reduction from VertexCover to Clique.
Your solution should have the following two steps:
i) First, show the reduction: specify how the inputs to VertexCover, G and k, can be transformed to a valid input pair, H and I, for Clique. Make sure to explain why this takes polynomial time.
ii) Second, show that the answer to Clique (H,1) can be converted to the answer of VertexCover (G, k). One possibility is to explain how a YES answer to Clique (H,l) also mean YES to VertexCover (G, k), AND a NO answer to VertexCover (H, 1) must also mean NO to Clique (G, k). (Hint: The claim we proved in part a) is an if and only if statement.)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
