Approximating clique is almost NP-complete

2002/12/09 by Uriel Feige, S. Goldwasser, László Lovász +2 · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Chordal graph #Clique #Clique problem #Combinatorics #Complexity and Algorithms in Graphs #Computational complexity theory #Computer science #Discrete mathematics #EXPTIME #Graph #Machine Learning and Algorithms #Mathematics #Omega #PSPACE #Pathwidth #Philosophy #Treewidth

paper · doi:10.1109/sfcs.1991.185341

openalex publication_date 2002/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

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

Citations

• The monotone circuit complexity of boolean functions
• Non-deterministic exponential time has two-prover interactive protocols
• A still better performance guarantee for approximate graph coloring

Cited by

• Probabilistic checking of proofs
• Approximating maximum independent sets by excluding subgraphs
• An effective local search for the maximum clique problem
• Vertex cover might be hard to approximate to within2−ε
• On the hardness of approximating vertex cover
• A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
• The importance of being biased
• Private information retrieval
• Clique is hard to approximate within n/sup 1-ε/
• Proof verification and hardness of approximation problems
• Approximate graph coloring by semidefinite programming
• Simple Constructions of Almost k‐wise Independent Random Variables
• Clique problem [wikipedia]