Editing Independent set (graph theory) (section)

{{Short description|Unrelated vertices in graphs}}

[[File:Independent set graph.svg|thumb|The nine blue vertices form a maximum independent set for the [[Generalized Petersen graph]] GP(12,4).]]

In [[graph theory]], an '''independent set''', '''stable set''', '''coclique''' or '''anticlique''' is a set of [[vertex (graph theory)|vertices]] in a [[Graph (discrete mathematics)|graph]], no two of which are adjacent. That is, it is a set <math>S</math> of vertices such that for every two vertices in <math>S</math>, there is no [[Edge (graph theory)|edge]] connecting the two. Equivalently, each edge in the graph has at most one endpoint in <math>S</math>. A set is independent if and only if it is a [[Clique (graph theory)|clique]] in the [[Complement graph|graph's complement]]. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.<ref>{{harvtxt|Korshunov|1974}}</ref>

A [[maximal independent set]] is an independent set that is not a [[proper subset]] of any other independent set.

A '''maximum independent set''' is an independent set of largest possible size for a given graph <math>G</math>. This size is called the '''independence number''' of ''<math>G</math>'' and is usually denoted by <math>\alpha(G)</math>.<ref>{{harvtxt|Godsil|Royle|2001}}, p. 3.</ref> The [[optimization problem]] of finding such a set is called the '''maximum independent set problem.''' It is a [[Strong NP-completeness|strongly NP-hard]] problem.<ref>{{Cite journal|last1=Garey|first1=M. R.|last2=Johnson|first2=D. S.|date=1978-07-01|title="Strong" NP-Completeness Results: Motivation, Examples, and Implications|journal=Journal of the ACM|volume=25|issue=3|pages=499–508|doi=10.1145/322077.322090|s2cid=18371269|issn=0004-5411|doi-access=free}}</ref> As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.

Every maximum independent set also is maximal, but the converse implication does not necessarily hold.