Independent Set

Input

Graph $G = (V, E)$ , positive integer $K \leq |V|$ .

Question

Does $G$ contain an independent set of size $K$ or more, i.e. a subset $V' \subseteq V$ with $|V'| \geq K$ such that no two vertices in $V'$ are joined by an edge in $E$ ?

Remains NP-complete for cubic planar graphs (Garey et al., 1976), (Garey & Johnson, 1977), (Maier & Storer, 1977), for edge graphs of directed graphs (Gavril, 1977), for total graphs of bipartite graphs (Yannakakis & Gavril, 1980), and for graphs containing no triangles (Poljak, 1974). Solvable in polynomial time for bipartite graphs (by matching, e.g. see (Harary, 1969)), for edge graphs (by matching), for graphs with no vertex degree exceeding 2, for chordal graphs (Gavril, 1972), for circle graphs (Gavril, 1973), for circular arc graphs (given their representation as families of arcs) (Gavril, 1974), for comparability graphs (Golumbic, 1977), and for claw-free graphs (Minty, 1980).

Proofs

NP-complete

Transformation from Vertex Cover.

Reducible from

Vertex Cover

References

Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237–267. https://doi.org/10.1016/0304-3975(76)90059-1
Garey, M. R., & Johnson, D. S. (1977). The Rectilinear Steiner Tree Problem is $NP$-Complete. SIAM Journal on Applied Mathematics, 32(4), 826–834. https://doi.org/10.1137/0132071
Maier, D., & Storer, J. (1977). A note on the complexity of the superstring problem Technical Report 233. Princeton University, Department of Electrical Engineering and Computer Science, Princeton, NJ.
Gavril, F. (1977). “Some NP-complete problems on graphs”, Proc. 11th Conf. on Information Sciences and Systems, Johns Hopkins University, Baltimore, MD.
Yannakakis, M., & Gavril, F. (1980). Edge Dominating Sets in Graphs. SIAM Journal on Applied Mathematics, 38(3), 364–372. https://doi.org/10.1137/0138030
Poljak, S. (1974). A note on stable sets and colorings of graphs. Commentationes Mathematicae Universitatis Carolinae, 15(2), 307–309. http://eudml.org/doc/16622
Harary, F. (1969). Graph theory. Addison-Wesley Publishing Company.
Gavril, F. (1972). Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. SIAM Journal on Computing, 1(2), 180–187. https://doi.org/10.1137/0201013
Gavril, F. (1973). Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks, 3(3), 261–273. https://doi.org/10.1002/net.3230030305
Gavril, F. (1974). Algorithms on circular-arc graphs. Networks, 4(4), 357–369. https://doi.org/10.1002/net.3230040407
Golumbic, M. C. (1977). The complexity of comparability graph recognition and coloring. Computing, 18(3), 199–208. https://doi.org/10.1007/bf02253207
Minty, G. J. (1980). On maximal independent sets of vertices in claw-free graphs. Journal of Combinatorial Theory, Series B, 28(3), 284–304. https://doi.org/10.1016/0095-8956(80)90074-x