Approximating clique is almost NP-complete

U. Feige, S. Goldwasser, L. Lovasz, S. Safra, M. Szegedy

Research output: Chapter in Book/Report/Conference proceedingConference contribution

194 Scopus citations

Abstract

The computational complexity of approximating ω(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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages2-12
Number of pages11
ISBN (Print)0818624450
StatePublished - Dec 1991
Externally publishedYes
EventProceedings of the 32nd Annual Symposium on Foundations of Computer Science - San Juan, PR, USA
Duration: Oct 1 1991Oct 4 1991

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

OtherProceedings of the 32nd Annual Symposium on Foundations of Computer Science
CitySan Juan, PR, USA
Period10/1/9110/4/91

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Approximating clique is almost NP-complete'. Together they form a unique fingerprint.

Cite this