# Independent set

Given a graph, $LaTeX: G=(V,E)$, an independent set (also called a stable set) is a subgraph induced by a subset of vertices, $LaTeX: S$, plus all edges with both endpoints in $LaTeX: 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, $LaTeX: w(v)$ for $LaTeX: v \in V$, the weight of an independent set, $LaTeX: S$, is the sum of the weights in $LaTeX: 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 $LaTeX: C$, since $LaTeX: V\backslash 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.)