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

a subset V' of vertices in an undirected graph G such that no pair of vertices in V' is joined by an edge of G

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.