Next:
MAXIMUM INDEPENDENT SET
Up:
Subgraphs and Supergraphs
Previous:
Subgraphs and Supergraphs
 
Index
M
AXIMUM
C
LIQUE
I
NSTANCE:
Graph
.
S
OLUTION:
A clique in
G
, i.e. a subset
such that every two vertices in
V'
are joined by an edge in
E
.
M
EASURE:
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=Z
PP
[
243
]. The same problem as M
AXIMUM
I
NDEPENDENT
S
ET
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
Viggo Kann
2000-03-20