In graph theory, a maximal independent set or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S. A maximal independent set is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so maximal independent sets are also called independent dominating sets. A graph may have many maximal independent sets of widely varying sizes; a largest maximal independent set is called a maximum independent set.
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}.
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.
Read more about Maximal Independent Set: Related Vertex Sets, Graph Family Characterizations, Bounding The Number of Sets, Set Listing Algorithms
Famous quotes containing the words independent and/or set:
“For myself I found that the occupation of a day-laborer was the most independent of any, especially as it required only thirty or forty days in a year to support one. The laborer’s day ends with the going down of the sun, and he is then free to devote himself to his chosen pursuit, independent of his labor; but his employer, who speculates from month to month, has no respite from one end of the year to the other.”
—Henry David Thoreau (1817–1862)
“Women are to be lifted up to a physical equality with man by placing upon their shoulders equal burdens of labor, equal responsibilities of state-craft; they are to be brought down from their altruistic heights by being released from all obligations of purity, loyalty, self-sacrifice, and made free of the world of passion and self-indulgence, after the model set them by men of low and materialistic ideals.”
—Caroline Fairfield Corbin (b. c. 1835–?)