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

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

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.