# Vertex cover

Given a graph, $LaTeX: \textstyle G = \left [ V, E \right ],$ a vertex cover is a subset of $LaTeX: V,$ say $LaTeX: C,$ such that for each edge $LaTeX: \textstyle (u,v) \in E,$ at least one of $LaTeX: u$ and $LaTeX: v$ is in $LaTeX: C.$ Given weights, $LaTeX: \{w(v)\}$ for $LaTeX: v \in V,$ the weight of a vertex cover is the sum of weights of the nodes in $LaTeX: C.$ The minimum weight vertex cover problem is to find a vertex cover whose weight is minimum. (Also see the covering problem and the maximum weight independent set problem.)