A set of vertices in an undirected graph where every edge connects at least one vertex. The vertex cover problem is to find a minimum size set and is NP-complete.