<p>We know that, unless P=NP, for any <span class="math-container">$\epsilon$</span> we can't distinguish in polynomial time between the two cases:</p>
<ol>
<li>There exists a clique of size at least <span class="math-container">$n^{1-\epsilon}$</span></li>
<li>All cliques have size at most <span class="math-container">$n^\epsilon$</span></li>
</ol>
<p>I'm interested in distinguishing between the following two cases:</p>
<ol>
<li>There exists a clique of size at least <span class="math-container">$n - n^{\epsilon}$</span>, <span class="math-container">$\epsilon &lt; 1$</span></li>
<li>All cliques have size at most <span class="math-container">$c \cdot n$</span>, <span class="math-container">$c &lt; 1$</span></li>
</ol>
<p>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).</p>
<p>I'll be very happy if the problem is hard for some fixed <span class="math-container">$\epsilon$</span> and <span class="math-container">$c$</span>.</p>

CC BY-SA 4.0
2022-02-06T20:33:51.553Z
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.
Laakeri
CC BY-SA 4.0
2022-02-07T06:57:52.180Z
Thank you very much!
Dmitry
<graph-theory><approximation-hardness><clique><independent-set>
Is finding a very large clique NP-hard?
Dmitry
# Is finding a very large clique NP-hard?

(Asked by: username_0 on 2022-02-06)

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

**Tags:** graph-theory, approximation-hardness, clique, independent-set
> **Comments:**
> **username_1**: 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.  
> **username_0**: Thank you very much!  

---

## 0 answers

