1
$\begingroup$

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?

$\endgroup$
0
2
$\begingroup$

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$.
$\endgroup$
1
  • $\begingroup$ I see - Every step is done in polynomial time and the number of iterations is bounded by $n$ (the complete graph). Nice, thank you! $\endgroup$ – Covvar Sep 16 '17 at 14:40
0
$\begingroup$

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.

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