Approximating Clique is Almost NP-Complete (Preliminary Version)

The computational complexity of approximating omega (G), the size of the largest clique in a graph G, within a given factor is considered. It is shown that if certain approximation procedures exist, then EXPTIME=NEXPTIME and NP=P. >

Authors

• Uriel Feige
• Shafi Goldwasser
• László Lovász 0001
• Muli Safra
• Mario Szegedy

Keywords

• Approximation algorithms
• Polynomials
• Computational complexity
• Protocols
• Testing
• Upper bound
• Data mining
• High Probability
• Running Time
• Estimation Algorithm
• Class Of Problems
• Estimation Problem
• Constant Factor
• Polynomial Of Degree
• Arbitrary Function
• Direct Line
• Information Bits
• Finite Field
• Exponential Time
• Arbitrary Field
• Random Bits
• Turing Machine
• Adjacent Vertices
• Vertex Cover
• Subset Of Vertices