reducing $CLIQUE$ from decision to search problem

Question

consider the language:$$CLIQUE = \left\{\langle G,k\rangle \ |\ \text{ $G$ is a graph containing a clique of size at least $k$ } \right\}$$

Suppose there's a polynomial time algorithm for $CLIQUE$. I need to show a polynomial time algorithm for finding a clique of size $k$.

Now, the idea is pretty easy if there's only one clique in the graph - You remove each vertex $v_i$ and query for $CLIQUE(G_i, k)$.

If there are two cliques in the graph this algorithm could not be applied since no matter which vertex will be removed there will always be a clique of size $k$.

An alternative would be removing each one of the ${m}\choose{k}$ but if $k = n/2$ for example, that wouldn't be a polynomial time algorithm anymore.

So my question is, can we solve this problem for the general case where there might be multiple cliques?

Answer 1

Keep removing vertices until the graph no longer contains a clique of size $k$, and let $v$ be the last vertex that you removed. It follows that there is some $k$-clique which contains $k$. Remove all vertices from the graph other than neighbors of $v$ (so $v$ itself is also removed), and recursively find a $(k-1)$-clique in the new graph. Add $v$ to this clique to create the desired $k$-clique.

The algorithm can also be formulated iteratively:

1. Let $C = \emptyset$ (this will be the clique).
2. Let $\ell = k$ (the current size of the clique).
3. Go over all vertices $v$ in the graph:
   • Check if after removing $v$ from the graph, the new graph still contains an $\ell$-clique.
   • If so, continue to the next vertex.
   • Otherwise, add $v$ to $C$, decrease $\ell$, and remove from the graph all vertices other than the neighbors of $v$.
4. Return $C$.

Answer 2

I think you can "strip the graph" until a $k$-clique remains instead of "building a $k$-clique":

1. Initially check for a $k$-clique, if none exists, return that answer.

2. Go through the vertices $v_1, v_2, \dotsc, v_n$. [One can terminate once $k$ vertices remain, but this is optional.]

   At each iteration, delete vertex $v_i$ and check for a $k$-clique.

   • If no $k$-clique exists in the remaining graph, then $v_i$ was "essential", i.e., in every $k$-clique of the graph prior to deletion, so add $v_i$ back!
   • If a $k$-clique still does exist, leave $v_i$ deleted

I'm quite sure this algorithm can be proven correct using the "essential vertex" definition. In contrast to the algorithm in Yuval's answer, the clique parameter $k$ stays the same throughout. So my algorithm is potentially less efficient, but maybe a tad easier to understand.