Independent set Guide, Meaning , Facts, Information and Description
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. Or, more simply put, a set of vertices such that none of them are connected by an edge. The size of a independent set is the number of vertices it contains.The maximum independent-set problem refers to the problem of finding the largest independent-set in any graph G. This problem is NP-complete, and as such, it is very unlikely that an efficient algorithm for finding the largest independent-set of a graph exists.
The opposite of a independent set is a clique. If we already know that the clique problem is NP-complete, then it is easy to prove, as the size of a independent set is the same as the size of the largest clique in the inverse graph.
Maximum independent set problem is not be confused with maximal independent set problem. 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 is solvable in polynomial time by a very simple algorithm. This algorithm starts with an empty set V. Then it searches for a vertex v that is not connected to any vertex in V and if such v is found, adds v to V. The algorithm stops when it cannot find v not connected to any vertex in V. This results in an independent set that is not contained in any larger independent set.
This is an Article on Independent set. Page Contains Information, Facts Details or Explanation Guide About Independent set