Independent set
From Wikipedia, the free encyclopedia
In graph theory, an independent, or stable set in a graph G, which contains vertices V, is a set of vertices V' (a subset of V) such that for every two vertices in V', there is no edge connecting the two. In other words, each edge in the graph is incident to at most one vertex in the set. 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. The problem of finding such a set is called the maximum independent set problem and is an NP-hard 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. However, the problem of finding the maximum independent set is NP-hard.
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.
[edit] See also
- an edge independent set is called Matching
