TOPICS
Search

Maximum Independent Set Problem

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 k and is NP-complete (Garey and Johnson 1983).

Song (2026) gave a deterministic approximation algorithm for an n-vertex graph with approximation ratio n/2^(Omega(sqrt(lnn))) and running time n^(O(sqrt(lnn))). The guarantee uses quasipolynomial time.

See also

Independence Number, Independent Set, Independent Vertex Set, Maximum Independent Vertex Set, Vertex Coloring Problem

Explore 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.Song, Z. "Improved Quasi-Polynomial-Time Approximation for Maximum Independent Set." 26 Oct 2026. https://arxiv.org/abs/2610.35228.

Referenced on Wolfram|Alpha

Maximum Independent Set Problem

Cite this as:

Weisstein, Eric W. "Maximum Independent Set Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MaximumIndependentSetProblem.html

Subject classifications