A note on the approximation of the MAX CLIQUE problem (Q1183423)

We show that all problems in MAX NP are strongly reducible to the MAX CLIQUE problem, that is, we polynomially reduce any problem in MAX NP to the MAX CLIQUE problem in such a way that there is a polynomial-time computable measure-preserving correspondence between the solutions of the two problems. It is well known that if the MAX CLIQUE problem admits a polynomial-time approximation algorithm, then it admits a polynomial-time approximation scheme [\textit{M. R. Carey} and \textit{D. Johnson}, J. Assoc. Comput. Mach. 23, 43-49 (1976; Zbl 0322.05111), \textit{C. Papadimitriou} and \textit{K. Steiglitz}, Combinatorial optimization: Algorithms and complexity, Englewood Cliffs/NJ: Prentice-Hall (1982; Zbl 0503.90060)]. Thus, as a consequence of our result, if the MAX CLIQUE problem is approximable, then every problem is MAX NP admits a polynomial-time approximation scheme. Since so far all attempts to obtain such a scheme were met with failure, our result makes the existence of a polynomial-time approximation algorithm for the MAX CLIQUE problem very doubtful. Recently, a different evidence that the problem MAX CLIQUE is not approximable has been given by \textit{U. Feige}, \textit{S. Goldwasser}, \textit{L. Lovasz}, \textit{S. Safra} and \textit{M. Szegedy} [Approximating clique is almost NP-complete, Proc. 32th FOCS (to appear)]: if the MAX CLIQUE problem is approximable in polynomial-time to within a factor of \(2^{(\log n)^{(1-\varepsilon)}}\), then NP is contained in the set of languages accepted in quasi-polynomial time (i.e., time \(2^{\log^ c n}\)). We observe that our result is closely related to a previous result obtained by \textit{P. Berman} and \textit{G. Schnitger} [On the complexity of approximating the independent set problem, Proc. 6th STACS, 256-268 (1989)] that connects the approximability of the MAX CLIQUE problem to the existence of a randomized polynomial-time approximation scheme for problems in MAX NP.