What does this sentence mean?

For all $ε > 0$, it is NP-hard to approximate MAX CLIQUE to within $n^{1 − ε}$.

Is the fact that complexity of approximation depends on $\epsilon$ hidden in the statement? I mean, if not, I guess we can make $\epsilon$ arbitrarily small, (like $\epsilon = 0.9999$), and get a very good approximation. So, I guess as we make $\epsilon$ smaller, the complexity should go remarkably higher. Right? In which order?


The sentence means that for every $\epsilon > 0$ there is a polytime reduction $f_\epsilon$ that takes an instance $\phi$ of SAT into a pair $(G,k)$ such that:

  • If $\phi$ is not satisfiable then $G$ has no $k$-clique.
  • If $\phi$ is satisfiable then $G$ has an $n^{1-\epsilon} k$-clique.

An $n^{1-\epsilon}$-approximation algorithm for MAX-CLIQUE can be used to distinguish the two cases.

The running time of $f_\epsilon$ indeed depends on $\epsilon$, which probably appears in the exponent, that is, $f_\epsilon$ runs in time $n^{g(\epsilon)}$, where $g(\epsilon)$ tends to $\infty$ as $\epsilon \to 0$.

  • $\begingroup$ Thanks. $\epsilon$ is between 0 and 1, right? I found a similar statement for minimum clique cover problem, that it is NP-hard to approximate it to within $n^{1-\epsilon}$. Does it mean that it is NP-hard to find a polynomial time $n$-approximation algorithm for minimum clique cover problem? $\endgroup$ – m0_as Jul 27 '17 at 6:54
  • $\begingroup$ The hardness only holds for $\epsilon > 0$. It is easy to come up with a polynomial time $n$-approximation algorithm. $\endgroup$ – Yuval Filmus Jul 27 '17 at 8:55
  • $\begingroup$ Yes, I meant $n^{1-\epsilon}$-approximation. One more question: If I have another problem and I can show that minimum clique cover problem can be reduced to that problem (which means it is harder than minimum clique cover problem), can I say the same statement for that? That is, It is NP-hard to approximate that problem within $n^{1-\epsilon}$? $\endgroup$ – m0_as Jul 27 '17 at 18:23
  • $\begingroup$ No. You need an approximation-preserving reduction. $\endgroup$ – Yuval Filmus Jul 27 '17 at 18:25
  • $\begingroup$ Can you be more specific? I meant I can reduce minimum clique cover problem to my problem in polynomial time. My problem is actually is quite similar to minimum clique cover problem in the sense that it has the same graph. So, if I find a solution to my question with an approximation bound, that exactly means that I can have a solution to minimum clique cover problem with that approximation bound, and vice-versa $\endgroup$ – m0_as Jul 27 '17 at 18:41

Let eps = 0.000001. It is NP-complete to find a clique within $N^{0.999999}$ of the maximum clique. But for N = 165,000, $N - N^{0.999999}$ < 2, so finding a clique of size 1 solves the problem, and this is quite trivial! So for tiny eps, the complexity is quite likely exponential, but even for quite large N, a solution is quite trivial.

Let eps = 0.999999. It is NP-complete to find a clique within $N^{0.000001}$ of the maximum clique. For $N ≤ 10^{300,000}$ this is equivalent to finding the maximum clique or a clique with one element less. Which is a little bit easier than finding the maximum clique, but not much. $N ≤ 10^{300,000}$ is obviously a lot larger than any problem that could ever be posed in this universe.


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.