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:
“The government is huge, stupid, greedy and makes nosy, officious and dangerous intrusions into the smallest corners of life—this much we can stand. But the real problem is that government is boring. We could cure or mitigate the other ills Washington visits on us if we could only bring ourselves to pay attention to Washington itself. But we cannot.”
—P.J. (Patrick Jake)