# 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?

## 1 Answer

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$.
• 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