The maximum independent set problem seeks a maximum independent vertex set in a given graph. The optimal
size is its independence number. The optimization
problem is NP-hard. Its decision version asks
whether the independence number is at least
a given integer 
and is NP-complete
(Garey and Johnson 1983).
Maximum Independent Set Problem
See also
Independence Number, Independent Set, Independent Vertex Set, Maximum Independent Vertex Set, Vertex Coloring ProblemExplore with Wolfram|Alpha
References
Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1983.Skiena, S. "Maximum Independent Set." §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.Referenced on Wolfram|Alpha
Maximum Independent Set ProblemCite this as:
Weisstein, Eric W. "Maximum Independent Set Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MaximumIndependentSetProblem.html