- INSTANCE: Graph .
- SOLUTION:
A clique in
*G*, i.e. a subset such that every two vertices in*V'*are joined by an edge in*E*. - MEASURE:
Cardinality of the clique, i.e., .

*Good News:*Approximable within [90].*Bad News:*Not approximable within for any [243].*Comment:*Not approximable within for any , unless NP=ZPP [243]. The same problem as MAXIMUM INDEPENDENT SET on the complementary graph. Approximable within if [14] and [367]. The same good news hold for the vertex weighted version [224].*Garey and Johnson:*GT19