MAXIMUM CLIQUE

Next: MAXIMUM INDEPENDENT SET Up: Subgraphs and Supergraphs Previous: Subgraphs and Supergraphs Index

INSTANCE: Graph $G=\left(V,E\right)$ .
SOLUTION: A clique in G, i.e. a subset $V' \subseteq V$ such that every two vertices in V' are joined by an edge in E.
MEASURE: Cardinality of the clique, i.e., $\vert V'\vert$ .
Good News: Approximable within $O\left(\vert V\vert/(\log \vert V\vert)^2\right)$ [90].
Bad News: Not approximable within $\vert V\vert^{1/2-\varepsilon }$ for any $\varepsilon >0$ [243].
Comment: Not approximable within $\vert V\vert^{1-\varepsilon }$ for any $\varepsilon >0$ , unless NP=ZPP [243]. The same problem as MAXIMUM INDEPENDENT SET on the complementary graph. Approximable within $\mbox{\sl opt}/O(m^{3(k+1)})$ if $\mbox{\sl opt}=\vert V\vert/k+m$ [14] and [367]. The same good news hold for the vertex weighted version [224].
Garey and Johnson: GT19

Viggo Kann
2000-03-20