0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Albjenow
    Jan 21, 2020 at 9:50
  • $\begingroup$ Please also read our reference question What is the definition of P, NP, NP-complete and NP-hard?. $\endgroup$
    – Pål GD
    Jan 21, 2020 at 9:59
  • $\begingroup$ The k-clique problem can easily be solved in O(n^k), for every fixed k. $\endgroup$
    – gnasher729
    Jan 21, 2020 at 13:27

0

Reset to default

Browse other questions tagged or ask your own question.