In computer science, the vertex cover problem is an NP-complete problem in complexity theory.

A vertex cover of an undirected graph G = (V,E) is a subset V' of the vertices of the graph which contains at least one of the two endpoints of each edge:

.

In the graph at the right, {1,3,5,6} is an example of a vertex cover.

The vertex cover problem is the optimization problem of finding a vertex cover of minimum size in a graph. The problem can also be stated as a decision problem:

INSTANCE: A graph G and a positive integer k.

QUESTION: Is there a vertex cover of size k or less for G?

Vertex cover is NP-complete, which means it is unlikely that there is an efficient algorithm to solve it. NP-completeness can be proven by reduction from 3-satisfiability.

Vertex cover is closely related to Independent Set problem by the theorem - a graph with n vertices has a vertex cover of size k if and only if the graph has an independence set of size n-k.

One can find a factor-2 approximation by repeatedly taking both endpoints of an edge into the vertex cover, removing them from the graph. No better constant-factor approximation is known; the problem is APX-complete , i.e., it cannot be approximated arbitrarily well.

A brute force algorithm to find a vertex cover in a graph is to list all subsets of vertices of size k and check each one to see whether it forms a vertex cover. This algorithm is exponential in k, but not in the size of the graph, i.e., vertex cover is fixed-parameter tractable with respect to k.

See also

• covering (graph theory)

Further reading

• Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, 1979.
• Preeti Patil & Sangita Patil. (Lecturer in Vartak Polytechnic) A Guide to the Theory of NP-Completeness. BPB & Co., Mumbai, 2004.