NP completeness (3) - Show that Set Cover is NP complete

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:

• 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!

NP completeness (2) - Show that k-Clique is NP complete

It is easy to show k-Clique is in NP, given a k-clique, 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. We need to verify that it is indeed a k-clique, which can be simply checked by testing all pairs are edges, which take times $ O(E) $ 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 the complement of the graph has a clique of $ k $ nodes. Note that the complement $ \bar{G} $of a graph $ G $ is defined by having the same vertex set, $ u $ and $ v $ are connected as an edge in $ \bar{G} $ if and only if they are not an edge in $ G $

Suppose there exists a clique of $ k $ nodes in $ \bar{G} $, we conclude that the same set of nodes is an independent set of $ G $. This is obvious because those nodes are all directly connected in $ \bar{G} $, and therefore not connected to each other in $ G $.

Suppose there does not exists a clique of $ k $ node in $ \bar{G} $, we conclude that there does not exists an independent set of $ k $ nodes, for if it does, it would have been the $ k $ clique in $ \bar{G} $.

With that, we can reduce the independent set problem to $ k $ clique, therefore $ k $ clique is NP complete.

NP completeness (1) - Vertex Cover

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.