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.
Read more about this topic: Vertex Cover
Famous quotes containing the word problem:
“Involuntary mental hospitalization is like slavery. Refining the standards for commitment is like prettifying the slave plantations. The problem is not how to improve commitment, but how to abolish it.”
—Thomas Szasz (b. 1920)