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

### MAXIMUM INDEPENDENT SET

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

- 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 [50] and for unit disk graphs [249]. The case of degree bounded by for is is APX-complete [371] and [69], is not approximable within for some [12], and not approximable within 1.0005 for B=3, 1.0018 for and 1.0030 for [70]. It is approximable within [69] for small , and within for larger values [275,13,437]. Also approximable on sparse graphs within where d is the average degree of the graph [211].

  Approximable within for k+1-claw free graphs [209]. The vertex weighted version is approximable within 3/2 for [231], within for [205], and within for larger values of [211].

  The related problem in hypergraphs is approximable within [211], 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 [434].

- Garey and Johnson: GT20

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