Maximal independent set

This article is about the combinatorial aspects of maximal independent sets of vertices in a graph. For stronger notion with a similar name, see Maximum independent set. For other aspects of independent vertex sets in graph theory, see Independent set (graph theory). For other kinds of independent sets, see Independent set (disambiguation).
The graph of the cube has six different independent sets (two of them are maximum), shown as the red vertices.

In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property.

For example, in the graph P3, a path with three vertices a, b, and c, and two edges ab and bc, the sets {b} and {a, c} are both maximally independent. The set {a} is independent, but is not maximal independent, because it is a subset of the larger independent set {a, c}. In this same graph, the maximal cliques are the sets {a, b} and {b, c}.

A MIS is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so MISs are also called independent dominating sets.

A P3 graph has two maximal independent sets. {a} or {c} alone forms an independent set, but it is not maximal.
The top two P3 graphs are maximal independent sets while the bottom two are independent sets, but not maximal. The maximum independent set is represented by the top left.

A graph may have many MISs of widely varying sizes;[a] the largest, or possibly several equally large, MISs of a graph is called a maximum independent set. The graphs in which all maximal independent sets have the same size are called well-covered graphs.

The phrase "maximal independent set" is also used to describe maximal subsets of independent elements in mathematical structures other than graphs, and in particular in vector spaces and matroids.

Independent sets for a star graph is an example of how vastly different the size of the maximal independent set can be to the maximum independent set. In this diagram, the star graph S8 has a maximal independent set of size 1 by selecting the internal node. It also has an maximal (and also maximum independent set) of size 8 by selecting each leave node instead.
Two independent sets for the star graph S8 show how vastly different in size two maximal independent sets (the right being maximum) can be.

Two algorithmic problems are associated with MISs: finding a single MIS in a given graph and listing all MISs in a given graph.
Cite error: There are <ref group=lower-alpha> tags or {{efn}} templates on this page, but the references will not show without a {{reflist|group=lower-alpha}} template or {{notelist}} template (see the help page).