** Next:** MAXIMUM INDEPENDENT SEQUENCE
** Up:** Subgraphs and Supergraphs
** Previous:** MAXIMUM CLIQUE
** Index**

- INSTANCE:
Graph
.
- SOLUTION:
An independent set of vertices, i.e. a subset
such that
no two vertices in
*V'* are joined by an edge in *E*.
- MEASURE:
Cardinality of the independent set, i.e., .

*Good News:*
See MAXIMUM CLIQUE.
*Bad News:*
See MAXIMUM CLIQUE.
*Comment:*
The same problem as MAXIMUM CLIQUE on the complementary graph.
Admits a PTAS for planar graphs [53]
and for unit disk graphs [264].
The case of degree bounded by
for
is
is APX-complete [393] and [75],
is not approximable within
for some
[12],
and not approximable within 1.0005 for *B=3*, 1.0018 for
and 1.0030
for
[76].
It is approximable within
[75] for small ,
and within
for larger values
[290,14,460].
Also approximable on sparse graphs within
where *d* is the
average degree of the graph [224].
Approximable within
for *k+1*-claw free graphs
[222].
The vertex weighted version is approximable within
3/2 for
[248], within
for
[218], and within
for larger values of
[224].
The related problem in hypergraphs is approximable within
[224], also in the weighted case.
MAXIMUM INDEPENDENT SET OF *K*-GONS, the variation in which the number of pairwise independent
*k*-gons (cycles of size *k*, )
is to be maximized
and where two *k*-gons are independent if any edge connecting
vertices from different *k*-gons must belong to at least one of these
*k*-gons, is not approximable within 4/3 for any .
It is not in
APX for any
unless NPQP [457].
*Garey and Johnson:* GT20

** Next:** MAXIMUM INDEPENDENT SEQUENCE
** Up:** Subgraphs and Supergraphs
** Previous:** MAXIMUM CLIQUE
** Index**
*Viggo Kann*

*2000-03-20*