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

### MAXIMUM CLIQUE

- 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., |V'|.

- Good News: Approximable within [83].

- Bad News: Not approximable within for any [63].

- Comment: Not approximable within for any , unless co-RP=NP [225]. The same problem as MAXIMUM INDEPENDENT SET on the complementary graph. Approximable within if [13] and [347]. The same good news hold for the vertex weighted version [211].

- Garey and Johnson: GT19