MAXIMUM INDEPENDENT SET

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: An independent set of vertices, i.e. a subset $V' \subseteq V$ such that no two vertices in V' are joined by an edge in E.
• MEASURE: Cardinality of the independent set, i.e., $\vert V'\vert$.

  
  

• 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 $\Delta$ for $\Delta\ge 3$ is is APX-complete [393] and [75], is not approximable within $\Delta^\varepsilon$ for some $\varepsilon >0$ [12], and not approximable within 1.0005 for B=3, 1.0018 for $\Delta=4$ and 1.0030 for $\Delta=5$ [76]. It is approximable within $(\Delta+3)/5$ [75] for small $\Delta$, and within $O(\Delta \log\log \Delta/\log \Delta)$ for larger values [290,14,460]. Also approximable on sparse graphs within $O(d \log\log d/\log d)$ where d is the average degree of the graph [224]. Approximable within $k/2+\varepsilon$ for k+1-claw free graphs [222]. The vertex weighted version is approximable within 3/2 for $\Delta=3$ [248], within $(\Delta+2)/3$ for $\Delta>3$ [218], and within $O(\Delta \log\log \Delta/\log \Delta)$ for larger values of $\Delta$ [224]. The related problem in hypergraphs is approximable within $O(\vert V\vert/ \log \vert V\vert)$ [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, $k\ge 3$) 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 $k\ge 3$. It is not in APX for any $k\ge g$ unless NP$\subset$QP [457].
• Garey and Johnson: GT20