# reducing $CLIQUE$ from decision to search problem

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?

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.
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.
• Otherwise, add $v$ to $C$, decrease $\ell$, and remove from the graph all vertices other than the neighbors of $v$.
4. Return $C$.
• I see - Every step is done in polynomial time and the number of iterations is bounded by $n$ (the complete graph). Nice, thank you! – Covvar Sep 16 '17 at 14:40