# Independent set

### From Glossary

Given a graph, , an *independent set* (also called a *stable set*) is a subgraph induced by a subset of vertices, , plus all edges with both endpoints in , 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, for , the weight of an independent set, , is the sum of the weights in . 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 , since
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.)