Given a graph, G=[V,E], an independent set is a subgraph induced by a subset of vertices, S, plus all edges with both endpoints in S, such that no two nodes in the subgraph are adjacent. A maximal independent set is one such that adding any node causes the subgraph to violate independence -- the added node is adjacent to some node already in the set. Given weights, {w(v)} for v in V, the weight of an independent set, S, is the sum of the weights in S. The maximum independent set problem is to find an independent set of maximum weight. This is equivalent to finding a minimum weight vertex cover, say C, since V\C is an independent set. (One can also refer to an independent set of arcs (or edges) as a subgraph with no two arcs (or edges) adjacent.)

Given a graph (, ), independent set is a subset of vertices of so that no pair of vertices defines an edge of . See a link on independent set.

a subset S of V which contains no edge