Vertex Cover - Computational Problem

Computational Problem

The minimum vertex cover problem is the optimization problem of finding a smallest vertex cover in a given graph.

INSTANCE: Graph

OUTPUT: Smallest number such that has a vertex cover of size .

If the problem is stated as a decision problem, it is called the vertex cover problem:

INSTANCE: Graph and positive integer .

QUESTION: Does have a vertex cover of size at most ?

The vertex cover problem is an NP-complete problem: it was one of Karp's 21 NP-complete problems. It is often used in computational complexity theory as a starting point for NP-hardness proofs.