A note on the approximation of the MAX CLIQUE problem
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.
- On the approximability of clique and related maximization problems
- The value of strong inapproximability results for clique
- Clique is hard to approximate within \(n^{1-o(1)}\)
- On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- scientific article; zbMATH DE number 4106276 (Why is no real title available?)
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- Logical definability of NP optimization problems
- On the complexity of approximating the independent set problem (extended abstract)
- The Complexity of Near-Optimal Graph Coloring
- Quantifiers and approximation
- The maximum clique problem
- Finding optimal subgraphs by local search
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Correction to: ``Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts
- Derandomized graph products
- Modelling competitive Hopfield networks for the maximum clique problem
- On the approximability of clique and related maximization problems
- Approximation and inapproximability results for maximum clique of disc graphs in high dimensions
- Extended and discretized formulations for the maximum clique problem
- Clique is hard to approximate within \(n^{1-o(1)}\)
- Maximum cut-clique problem: ILS heuristics and a data analysis application
- scientific article; zbMATH DE number 5997363 (Why is no real title available?)
- The value of strong inapproximability results for clique
- ON TWO APPROXIMATION ALGORITHMS FOR THE CLIQUE PROBLEM
- scientific article; zbMATH DE number 1860650 (Why is no real title available?)
- On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
- Approximate solution of NP optimization problems
- A note on the descriptive complexity of maximization problems
- On the complexity of the shortest-path broadcast problem
This page was built for publication: A note on the approximation of the MAX CLIQUE problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1183423)