I am reading a proof on CLIQUE is NP-Complete. The first step is of course to show that CLIQUE is NP.
c is the clique certificate
V = “On input $\langle\langle G, k\rangle, c\rangle$:
- Test whether c is a set of k different nodes in G.
- Test whether G contains all edges connecting nodes in c.
- If both tests pass, accept; otherwise, reject.”
Is c just some arbitrary chosen set of k nodes? How would complexity analysis for 1 and 2 give polynomial time?
To test whether $c$ is a set of $k$ different nodes in $G$ will going to take $O(c^2)$ time (just check for every possible pair). Now you want to check whether $c$ forms a clique, to do so you need to check every possible edge i.e. $O(c^2)$ into time to check edge is present between a pair or not. So time taken for step 1 and 2 is $O(c^2)$ + $O(c^2)$ i.e $O(c^2)$ polynomial in the input size.
You don't need to worry about $c$, it is a part of input or particularly certificate.
This is a very basic question, which suggests you should review some earlier material from your course.
$c$ isn't chosen: it's the input that's given to you. It's the thing you're trying to verify. Note that the question doesn't specify the format of $c$, so you can choose anything reasonable. For example, if the vertices of the graph are $1, \dots, v$, then $c$ could be a list of numbers written in unary or binary, or it could be a string of $v$ bits, where the $i$th bit is $1$ iff the $i$th vertex is in the set.
To test whether $c$ has the desired properties, you just need to loop through the elements of $c$ and check that they're all different, that there are at least $k$ of them and that they meet the definition of a clique. Think about how you'd do that with a pencil and paper, and that will give you an algorithm. Analyze how many steps that will take in terms of the size of $c$ and that will give you your polynomial bound.
