A
vertex cover is a
set of
vertices 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.