# Is finding a very large clique NP-hard?

We know that, unless P=NP, for any $$\epsilon$$ we can't distinguish in polynomial time between the two cases:

1. There exists a clique of size at least $$n^{1-\epsilon}$$
2. All cliques have size at most $$n^\epsilon$$

I'm interested in distinguishing between the following two cases:

1. There exists a clique of size at least $$n - n^{\epsilon}$$, $$\epsilon < 1$$
2. All cliques have size at most $$c \cdot n$$, $$c < 1$$

Is anything known about this (or similar) problem? I would actually expect this to be in P, but I seem to find counter-examples for simple algorithms I try to apply (e.g. trying to grow the clique one vertex at a time breaks if we randomly remove some fraction of edges outside of the clique).

I'll be very happy if the problem is hard for some fixed $$\epsilon$$ and $$c$$.

• Let $k$ be the minimum number such that there exists a clique of size $n-k$. Now, $k$ is the equivalent to the minimum vertex cover of the complement, so it can be 2-approximated in polynomial time. Feb 6 at 20:33
• Thank you very much! Feb 7 at 6:57