1
$\begingroup$

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$:

  1. Test whether c is a set of k different nodes in G.
  2. Test whether G contains all edges connecting nodes in c.
  3. 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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.