Problem:
Prove that Vertex Cover is NP complete.
Solution:
We will assume the independent set problem is NP complete.
It is easy to show Vertex Cover is in NP, given a vertex cover, we can use it as the certificate. The size of the certificate is at most the number of nodes, which is polynomial of the input size. Given the certificate, we can simply iterate through the set of all edges and check that the given node indeed cover all edges, such an algorithm that $ O(E) $ time and is certainly polynomial in time in the input size.
To prove that it is NP complete, we reduce the independent set problem to it.
Suppose we need to solve the problem that whether or not a graph of $ |V| $ node contains an independent set of $ k $ nodes, we can solve the problem by asking whether or not we have a vertex cover of $ |V| - k $ nodes.
Suppose there exists a vertex cover of $ |V| - k $ nodes, we claim the complement of the vertex cover is an independent set. Indeed, if the complement is not an independent set, then there exists an edge such that both end points is in the complement, that means both end points were not in the vertex cover, of course that is impossible because a vertex cover must cover all edges.
Suppose there does not exist a vertex cover of $ |V| - k $ nodes, then we claim that there does not exist an independent set of $ k $ node. If there does exist an independent set of $ k $ nodes, we claim that the complement of the independent set is a vertex cover. Indeed, if the complement is not a vertex cover, then there must exists an edge that is does not cover, but that would mean both ends on that edge is included in the independent set, which is clearly impossible.
With that, we conclude that we can reduce independent set, a known NP complete problem, to vertex cover, therefore, vertex cover is NP complete too.
Prove that Vertex Cover is NP complete.
Solution:
We will assume the independent set problem is NP complete.
It is easy to show Vertex Cover is in NP, given a vertex cover, we can use it as the certificate. The size of the certificate is at most the number of nodes, which is polynomial of the input size. Given the certificate, we can simply iterate through the set of all edges and check that the given node indeed cover all edges, such an algorithm that $ O(E) $ time and is certainly polynomial in time in the input size.
To prove that it is NP complete, we reduce the independent set problem to it.
Suppose we need to solve the problem that whether or not a graph of $ |V| $ node contains an independent set of $ k $ nodes, we can solve the problem by asking whether or not we have a vertex cover of $ |V| - k $ nodes.
Suppose there exists a vertex cover of $ |V| - k $ nodes, we claim the complement of the vertex cover is an independent set. Indeed, if the complement is not an independent set, then there exists an edge such that both end points is in the complement, that means both end points were not in the vertex cover, of course that is impossible because a vertex cover must cover all edges.
Suppose there does not exist a vertex cover of $ |V| - k $ nodes, then we claim that there does not exist an independent set of $ k $ node. If there does exist an independent set of $ k $ nodes, we claim that the complement of the independent set is a vertex cover. Indeed, if the complement is not a vertex cover, then there must exists an edge that is does not cover, but that would mean both ends on that edge is included in the independent set, which is clearly impossible.
With that, we conclude that we can reduce independent set, a known NP complete problem, to vertex cover, therefore, vertex cover is NP complete too.
No comments :
Post a Comment