Independent set (graph theory)
From Wikipedia, the free encyclopedia
 |
It has been suggested that Independent set problem be merged into this article or section. (Discuss) |
In graph theory, an independent set or stable set is a set of vertices in a graph no two of which are adjacent. That is, it is a set V of vertices such that for every two vertices in V, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in V. The size of an independent set is the number of vertices it contains.
A maximal independent set is an independent set such that adding any other node to the set forces the set to contain an edge.
A maximum independent set is a largest independent set for a given graph G and its size is denoted α(G).[1] The problem of finding such a set is called the maximum independent set problem and is an NP-complete problem. As such, it is very unlikely that an efficient algorithm for finding a maximum independent set of a graph exists.
The problem of deciding if a graph has an independent set of a particular size is the independent set problem. It is computationally equivalent to deciding if a graph has a clique of a particular size. This follows from the fact that if a graph has an independent set of size k, then its complement (the graph on the same vertex set, but complementary edge set) has a clique of size k. The decision version of Independent Set (and consequently, clique) is known to be NP-complete.
A maximum independent set should not be confused with a maximal independent set. A maximal independent set is an independent set which is not contained in any larger independent set. The problem of finding a maximal independent set can be solved in polynomial time by a trivial greedy algorithm.
Contents |
[edit] Properties
[edit] Relationship to other graph parameters
A set is independent if and only if it is a clique in the graph’s complement, so the two concepts are complementary. In fact, sufficiently large graphs with no large cliques have large independent sets, a theme that is explored in Ramsey theory.
A set is independent if and only if its complement is a vertex cover. The sum of α(G) and the size minimum vertex cover β(G) is the number of vertices in the graph.
In a bipartite graph, the number of vertices in a maximum independent set equals the number of edges in a minimum edge covering.
[edit] Maximal independent set
An independent set that is not the subset of another independent set is called maximal. Such sets are dominating sets. Graphs contain at most 3n/3 maximal independent sets, but many graphs have far fewer. The number of maximal independent sets in n-vertex cycle graphs is given by the Perrin numbers, and the number of maximal independent sets in n-vertex path graphs is given by the Padovan sequence.[2] Therefore, both numbers are proportional to powers of 1.324718, the plastic number. Listing the maximal independent sets can be used as a subroutine for many algorithms that deal with NP-hard problem.
[edit] See also
- An edge-independent set is called a matching.
[edit] Notes
- ^ Godsil & Royle 2004, p.3
- ^ Füredi, Z. (1987). "The number of maximal independent sets in connected graphs". Journal of Graph Theory 11 (4): 463–470. doi:.
[edit] References
- Godsil, Chris; Gordon Royle (2004) [1949]. Algebraic Graph Theory. New York: Springer. ISBN 0-387-95220-9.
