display | more...
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.

Log in or register to write something here or to contact authors.