Approximating clique is almost NP-complete
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 349, 2-12
- https://doi.org/10.1109/sfcs.1991.185341
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 Nature ,1991
- Approximating maximum independent sets by excluding subgraphsPublished by Springer Nature ,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 Nature ,1972