Clique is hard to approximate within n/sup 1-ε/

2002/12/24 by Johan Håstad · 5 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Formal Methods in Verification #Cryptography and Data Security #Clique #Lemma (botany) #Combinatorics #Mathematics #Polynomial #Function (biology) #Discrete mathematics #Consistency (knowledge bases) #Mathematical analysis

paper · doi:10.1109/sfcs.1996.548522

openalex publication_date 2002/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

The author proves that unless NP=coR, Max Clique is hard to approximate in polynomial time within a factor n/sup 1-/spl epsiv// for any /spl epsiv/>0. This is done by, for any /spl delta/>0, constructing a proof system for NP which uses /spl delta/ amortized free bits. A central lemma, which might be of independent interest, gives sufficient conditions (in the form of a certain type of agreement) for creating a global function from local functions certain local consistency conditions.

Citations

• On Unapproximable Versions of NP-Complete Problems
• The complexity of theorem-proving procedures
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• On the complexity of approximating the independent set problem
• Algebraic methods for interactive proof systems
• Interactive proofs and the hardness of approximating cliques
• Approximating maximum independent sets by excluding subgraphs
• Probabilistic checking of proofs; a new characterization of NP
• Approximating clique is almost NP-complete
• Proof verification and hardness of approximation problems

Cited by

• A new point of NP-hardness for unique games
• Vertex cover might be hard to approximate to within2−ε
• Approximate the k-Set Packing Problem by Local Improvements
• Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes
• Induced path [wikipedia]