# Independent set (graph theory)
An **independent set** in a graph is a subset of vertices in which no two vertices are adjacent, that is, no edge of the graph connects any pair of them.[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf) The size of the largest independent set in a graph G is called the independence number, written \( \alpha(G) \) (also the stability number).[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf) • [2](https://arxiv.org/abs/1709.02475) Finding a maximum independent set is one of the central computational problems of graph theory: it is NP-hard in general, hard to approximate, but tractable for several important graph classes.[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf)
| Key fact | Detail |
|---|---|
| Definition | A subset of vertices with no edges between any pair of its vertices[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf) |
| Independence number | \( \alpha(G) \), the size of a maximum independent set; for the 5-cycle, \( \alpha(C_5) = 2 \)[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf) • [3](https://www.mathwords.com/i/independent_set.htm) |
| General complexity | Computing \( \alpha(G) \) is NP-hard, and approximating it within a constant factor in polynomial time is also NP-hard[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf) |
| Complement relation | Maximum independent set in G is the same problem as maximum clique in the complement graph \( \overline{G} \)[4](https://www.csc.kth.se/tcs/compendium/node34.html) |
| Easy cases | Polynomial time on bipartite graphs (by König's theorem), and on claw-free, P5-free, and perfect graphs[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf) |
| Exact exponential algorithms | Solvable in \( 1.1996^{n} \cdot n^{O(1)} \) time with polynomial space (Xiao and Nagamochi, 2017)[5](https://arxiv.org/abs/1312.6260) |
## Definition and basic examples
Given a graph G with vertex set V, a subset I of V is an independent set of G if there are no edges between any pair of vertices in I.[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf) • [6](https://www.cse.iitd.ac.in/~rjaiswal/2016/col351/Notes/Week-13/lec-1.pdf) A set is *maximal* if no vertex can be added to it while keeping independence, and *maximum* if no independent set in the graph has more vertices; the maximum size is the independence number \( \alpha(G) \).[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf) • [3](https://www.mathwords.com/i/independent_set.htm)
The distinction matters in practice. In a 5-cycle, every maximum independent set has two vertices, such as \{1, 3\} or \{2, 5\}, so \( \alpha(C_5) = 2 \), and there are five different maximum sets.[3](https://www.mathwords.com/i/independent_set.htm) A greedy procedure that simply adds vertices one at a time produces a maximal set, which can be much smaller than a maximum one; the lexicographically first maximal independent set of a graph depends on the vertex ordering used.[7](https://www.sciencedirect.com/topics/computer-science/independent-set)
A generalization is the k-independent set, a vertex set S such that the maximum degree in the graph induced by S is at most k; the usual independent set is the case k = 0, and the corresponding parameter is the k-independence number.[8](https://arxiv.org/abs/1208.4734)
## Relation to other graph problems
**Complementarity.** The maximum independent set problem is the same problem as MAXIMUM CLIQUE on the complementary graph, in which adjacent vertices become non-adjacent and vice versa.[4](https://www.csc.kth.se/tcs/compendium/node34.html) The same holds in the weighted case: a maximum weight independent set in G is a maximum weight clique in \( \overline{G} \).[9](https://arxiv.org/abs/1810.10834)
**Vertex cover.** The vertices not in an independent set form a vertex cover, a set touching every edge. For bipartite graphs, and in particular trees, König's theorem states that all vertices not in a minimum vertex cover can be included in a maximum independent set, so the independence number can be found in polynomial time there.[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf) On trees the independence number also coincides with the edge cover number, and together with the matching number it accounts for all vertices.[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf)
## Computational complexity
Computing \( \alpha(G) \) is NP-hard in general, and the problem remains NP-complete even when restricted to planar graphs.[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf) • [10](https://epubs.siam.org/doi/abs/10.1137/0211055?journalCode=smjcat) [Approximation](https://www.edgepedia.org/approximation) is also hard: in general it is not possible to approximate the independence number up to a constant factor in polynomial time.[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf)
**Tractable classes.** Polynomial-time exact algorithms are known for special graph classes, including [claw-free graphs](https://www.edgepedia.org/claw-free-graph), P5-free graphs, and perfect graphs.[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf) For planar graphs, and more generally for graphs closed under taking minors, polynomial-time approximation schemes exist.[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf) An early result of Chiba, Nishizeki, and Saito finds, for a planar graph with any number n of vertices, an independent set larger than half a maximum independent set in \( O(n \log n) \) time, an absolute worst-case ratio greater than \( \tfrac{1}{2} \).[10](https://epubs.siam.org/doi/abs/10.1137/0211055?journalCode=smjcat)
**Exact exponential algorithms.** For instances that must be solved exactly, the best known bounds are exponential but far below exhaustive search. Xiao and Nagamochi showed that maximum independent set on an n-vertex graph can be solved in \( 1.1996^{n} \cdot n^{O(1)} \) time and polynomial space, improving on Robson's \( 1.2109^{n} \cdot n^{O(1)} \)-time exponential-space algorithm published in 1986; for graphs of maximum degree 6 and 7 their algorithms run in \( 1.1893^{n} \cdot n^{O(1)} \) and \( 1.1970^{n} \cdot n^{O(1)} \) time.[5](https://arxiv.org/abs/1312.6260) These branch-and-reduce algorithms use fast algorithms for low-degree graphs hierarchically together with a careful analysis of bounded-degree structure.[5](https://arxiv.org/abs/1312.6260)
## Algorithms in practice
The most efficient practical algorithms for maximum independent set, in both theory and practice, use reduction rules to shrink the input to a much smaller equivalent instance called a kernel, which is then solved exactly.[11](https://doi.org/10.1145/3355502) Branch-and-reduce search, branch-and-bound interleaved with reductions that decrease the input size, has been especially effective.[9](https://arxiv.org/abs/1810.10834)
For the weighted version, in which each vertex carries a weight and the goal is a maximum total weight independent set, Lamm, Schulz, Strash, and colleagues developed a suite of reductions and tested them on real-world graphs of up to millions of vertices and edges. On many instances, their branch-and-reduce method ran as much as two orders of magnitude faster than the inexact local search methods then available, and it finished most of them in under 15 minutes; on the instances left unsolved, adding kernelization to local search yielded solutions of better quality than local search by itself.[9](https://arxiv.org/abs/1810.10834) Branching strategy also matters: targeted rules that decompose the graph into components or remove vertices blocking reductions outperformed the default highest-degree rule on 65 percent of tested instances, with a speedup of 2.29 on sparse networks.[12](https://arxiv.org/abs/2102.01540)
## Applications
The independence number is a well-known graph parameter with applications in scheduling theory, coding theory, and collusion detection in voting pools, and it has attracted particular interest in theoretical computer science.[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf) In the weighted setting, applications span signal transmission, information retrieval, and computer vision; a concrete example is map labeling, where the label conflict graph connects any two overlapping labels with an edge, vertices carry weights proportional to a city's population, and a maximum weight independent set picks the largest set of visible non-overlapping labels.[9](https://arxiv.org/abs/1810.10834) The generalized independent set problem, a generalization of the classical problem, has practical applications in forest harvesting and image and video processing.[13](https://www.sciencedirect.com/science/article/pii/S0305054824000339)
## Extremal and structural theory
Independent sets sit at the center of extremal combinatorics through the Ramsey and Turán theorems, both among the most well-known theorems of graph theory.[14](https://renyi.hu/~sos/1994_Turan_Ramsey_Theoremes_And_Kp_Independence_Numbers.pdf) Ramsey–Turán theory asks a combined question: what is the maximum number of edges an n-vertex graph can have without containing a given graph L as a subgraph, while also having no more than f(n) independent vertices; the problem is motivated by the classical Turán and Ramsey theorems and by applications of [Turán's theorem](https://www.edgepedia.org/turans-theorem) to geometry and analysis, in particular potential theory.[15](https://real.mtak.hu/110601/) Turán himself arrived at the extremal problem that became Turán's theorem in 1941 through [Ramsey's theorem](https://www.edgepedia.org/ramseys-theorem) during the 1940s.[16](https://page.mi.fu-berlin.de/szabo/PDF/notes.pdf) In combinatorics, the independence number has received considerable attention starting with early work by Béla Bollobás.[1](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf)
## References
1. [Independence and domination number of random trees (Holmgren, Mitsche, Noy), University of Frankfurt](https://www.math.uni-frankfurt.de/~neiningr/ind_set.pdf)
2. [Maximum independent sets near the upper bound, arXiv](https://arxiv.org/abs/1709.02475)
3. [Independent Set — Definition, Formula & Examples, MathWorld companion (Mathwords)](https://www.mathwords.com/i/independent_set.htm)
4. [Maximum Independent Set, KTH compendium](https://www.csc.kth.se/tcs/compendium/node34.html)
5. [Mingyu Xiao and Hiroshi Nagamochi (2017). Exact algorithms for maximum independent set. Information and Computation 255: 126–146; arXiv version](https://arxiv.org/abs/1312.6260)
6. [Independent Set definition, IIT Delhi COL351 lecture notes](https://www.cse.iitd.ac.in/~rjaiswal/2016/col351/Notes/Week-13/lec-1.pdf)
7. [Independent Set — an overview, ScienceDirect Topics](https://www.sciencedirect.com/topics/computer-science/independent-set)
8. [New approach to the k-independence number of a graph, arXiv](https://arxiv.org/abs/1208.4734)
9. [Lamm, Schulz, Strash, Williger, Zhang (2018). Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs, arXiv](https://arxiv.org/abs/1810.10834)
10. [Chiba, Nishizeki, Saito. An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs. SIAM Journal on Computing](https://epubs.siam.org/doi/abs/10.1137/0211055?journalCode=smjcat)
11. [Scalable Kernelization for Maximum Independent Sets, ACM Journal of Experimental Algorithmics](https://doi.org/10.1145/3355502)
12. [Hespe, Lamm, Schorr (2021). Targeted Branching for the Maximum Independent Set Problem, SEA 2021, arXiv](https://arxiv.org/abs/2102.01540)
13. [Exact and heuristic solution approaches for the Generalized Independent Set Problem, Computers & Operations Research](https://www.sciencedirect.com/science/article/pii/S0305054824000339)
14. [Turán–Ramsey Theorems and Kp-Independence Numbers, Rényi Institute](https://renyi.hu/~sos/1994_Turan_Ramsey_Theoremes_And_Kp_Independence_Numbers.pdf)
15. [Turán–Ramsey theorems and simple asymptotically extremal structures, Repository of the Hungarian Academy](https://real.mtak.hu/110601/)
16. [Ramsey-type problems lecture notes, Freie Universität Berlin](https://page.mi.fu-berlin.de/szabo/PDF/notes.pdf)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Graph invariants and parameters › Clique, independence, and homomorphism invariants*
*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license