A vertex cover
is a set
in a graph
such that every edge
in the graph is incident
(connected) to at least one vertex in the set. The set of all vertices, for example, is a vertex cover
The vertex cover problem is: given a graph and an integer k, is there a vertex cover for the graph with <= k vertices?
It has been proven that the vertex cover problem is NP-complete. However, it is possible to answer the vertex cover problem for bipartite graphs in polynomial time.