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.
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.
No comments :
Post a Comment