An independent set
, in graph theory
, is a set of vertices that are not connected
to each other by an edge
. Any set with exactly one vertex
is an independent set.
The independent set problem is: given a graph and an integer k, is there an independent set with the number of vertices >= k?
The independent set problem has been proven to be np-complete by a reduction from clique.