Independent set
|
|
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 maximum independent set is the largest independent set for a given graph. The problem of finding this set is called independent set problem and is a NP-complete problem. As such, it is very unlikely that an efficient algorithm for finding the largest independent-set of a graph exists.
The opposite of an independent set is a clique, in the sense that every independent set corresponds to a clique in the complement graph. It fact, the independent set problem and the clique problem are equivalent, in the sense that if we know one is NP-complete, we can easily show that the other is NP-complete, and most algorithms for solving one problem can be transformed into an algorithm which solves the other in the same time and space.
A maximum independent set problem 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.
See also
- an edge independent set is called Matchingde:Independent Set