= 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.
Back to article page