Next: MAXIMUM INDEPENDENT SET
Up: Subgraphs and Supergraphs
Previous: Subgraphs and Supergraphs
  Index
- 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
Viggo Kann
1999-04-22