# Is $k$-Clique NP-hard? [duplicate]

On my lecture note it was written that "Finding a clique of size $$k$$ in a graph is NP".

Later in an example for reduction the following was written:

"Assume we know how to answer "Is there a clique of size $$k$$ in a graph", then each time we will hide one node of the graph an on the newly created graph we will check Is there a clique of size $$k$$ in a graph:

If there is a clique of size $$k$$ and the node is not a part of the clique

If there is no clique of size $$k$$ and the node is part of the clique

I have read more about it, and wanted to be sure I have understand this example.

1. Given a graph, answering the question whereas or not it has clique of size $$k$$ is NP

2. Given a graph, printing a clique of size $$k$$ is P

If it is correct then this is an example why NP is a problem (1) that the verifier (2) is P?

• You seem to confuse to different dichotomies here. Firstly, the distinction between the (general) Clique problem where $k$ is part of the input and the family of $k$-Clique probems where $k$ is fixed for each problem. Secondly, the distinction between the decision problem of Clique and the corresponding search problem. Jan 21 '20 at 9:50
• Please also read our reference question What is the definition of P, NP, NP-complete and NP-hard?. Jan 21 '20 at 9:59
• The k-clique problem can easily be solved in O(n^k), for every fixed k. Jan 21 '20 at 13:27