1
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – Laakeri
    Feb 6 at 20:33
  • $\begingroup$ Thank you very much! $\endgroup$
    – Dmitry
    Feb 7 at 6:57

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.