Maximal independent set (source code)

= Maximal independent set

A <maximal independent set> is an <independent set> that cannot be enlarged by adding another vertex. Equivalently, every vertex outside it has a neighbor inside it. This is maximality by inclusion, rather than maximum possible size.

In a three-vertex path, the middle vertex alone is a <maximal independent set>, as is the set containing both endpoints. Only the latter is a <maximum independent set>. A greedy procedure that repeatedly chooses a vertex and excludes its neighbors finds a <maximal independent set>, but can miss a maximum one. The distinction is important in approximation and scheduling algorithms.