Problem 1 - Prove that Set Cover is in NP.
We will use the set ids as a certificate. The number of set ids is at most $ n $ and therefore the size of the certificate is $ O(n) $ and is polynomial in the size of the problem.
To verify the solution, we can check that there are $ k $ set ids, and their union is the universal set. Checking there are $ k $ set ids take $ O(1) $ time, and checking if the union covers the set take at most $ O(k) \times O(|P|) $ time, where $ |P| $ is the problem size, therefore, we can check if a certificate is valid in polynomial time.
Therefore k-SET Cover is in NP.
Problem 2 - Show that Set-Cover in NP complete
In problem 1 - we have already shown Set-Cover is in NP, so all we have to do is to reduce Vertex Cover to Set Cover. The key idea is that we map an edge to be an element in the set cover problem, and a node into a set of edges that it connects to. Now, the problem of choosing a subset of node to cover all edges becomes choosing the set of edges corresponding to the node to cover the edges, the latter is obviously a set cover problem.
Suppose there exists a set-cover of $ k $ sets, we know each of these $ k $ set corresponding to exactly one node. We claim that the nodes corresponding to the set is indeed a vertex cover. We know that the $ k $ set cover all edges, in particular, for any edge $ e $, there exists at least one set $ x $ cover it. The node $ n $ corresponding to $ x $ must have $ e $ connected to it, so $ e $ is covered. Because that must be true for all edges, we conclude when the set cover problem found a set cover, we also find a vertex cover.
Suppose there does not exist a set-cover of $ k $ sets, and suppose there does exist a vertex-cover of $ k $ vertices, we will derive a contradiction. That will conclude our proof because we show that if set-cover reports there is no set-cover, there is no vertex cover. Consider the sets associated with the $ k $ vertices, this must include all edges because it is a vertex cover, therefore, there does exist a $ k $ set-cover, so we reached the desired contradiction.
Last but not least, the mapping from a node to a set can spend at most $ |p|^2 $ time (in the worst case of a complete graph), therefore the reduction takes polynomial time.
To summarize, we have shown:
Therefore we gladly conclude set-cover in NP complete!
We will use the set ids as a certificate. The number of set ids is at most $ n $ and therefore the size of the certificate is $ O(n) $ and is polynomial in the size of the problem.
To verify the solution, we can check that there are $ k $ set ids, and their union is the universal set. Checking there are $ k $ set ids take $ O(1) $ time, and checking if the union covers the set take at most $ O(k) \times O(|P|) $ time, where $ |P| $ is the problem size, therefore, we can check if a certificate is valid in polynomial time.
Therefore k-SET Cover is in NP.
Problem 2 - Show that Set-Cover in NP complete
In problem 1 - we have already shown Set-Cover is in NP, so all we have to do is to reduce Vertex Cover to Set Cover. The key idea is that we map an edge to be an element in the set cover problem, and a node into a set of edges that it connects to. Now, the problem of choosing a subset of node to cover all edges becomes choosing the set of edges corresponding to the node to cover the edges, the latter is obviously a set cover problem.
Suppose there exists a set-cover of $ k $ sets, we know each of these $ k $ set corresponding to exactly one node. We claim that the nodes corresponding to the set is indeed a vertex cover. We know that the $ k $ set cover all edges, in particular, for any edge $ e $, there exists at least one set $ x $ cover it. The node $ n $ corresponding to $ x $ must have $ e $ connected to it, so $ e $ is covered. Because that must be true for all edges, we conclude when the set cover problem found a set cover, we also find a vertex cover.
Suppose there does not exist a set-cover of $ k $ sets, and suppose there does exist a vertex-cover of $ k $ vertices, we will derive a contradiction. That will conclude our proof because we show that if set-cover reports there is no set-cover, there is no vertex cover. Consider the sets associated with the $ k $ vertices, this must include all edges because it is a vertex cover, therefore, there does exist a $ k $ set-cover, so we reached the desired contradiction.
Last but not least, the mapping from a node to a set can spend at most $ |p|^2 $ time (in the worst case of a complete graph), therefore the reduction takes polynomial time.
To summarize, we have shown:
- Set cover is in NP - in problem 1
- A vertex cover problem instance can transform into a to set cover problem instance in polynomial time - the last part above
- The transformation preserve yes instances - the first proof
- The transformation preserve no instances - the second proof
Therefore we gladly conclude set-cover in NP complete!
No comments :
Post a Comment