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

## 2 Answers

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! Sep 16 '17 at 14:40

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.