Approximating clique is almost NP-complete
- 9 December 2002
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE) in [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science
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.Keywords
This publication has 18 references indexed in Scilit:
- Multi-oracle interactive protocols with space bounded verifiersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Algebraic methods for interactive proof systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the power of multi-prover interactive protocolsTheoretical Computer Science, 1994
- The complexity of the max word problemPublished by Springer Science and Business Media LLC ,1991
- Approximating maximum independent sets by excluding subgraphsLecture Notes in Computer Science, 1990
- On the power of two-point based samplingJournal of Complexity, 1989
- Graph products and chromatic numbersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- On the complexity of space bounded interactive proofsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Multi-prover interactive proofs: how to remove intractabilityPublished by Association for Computing Machinery (ACM) ,1988
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972