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:
“A curious thing about the ontological problem is its simplicity. It can be put in three Anglo-Saxon monosyllables: ‘What is there?’ It can be answered, moveover, in a word—‘Everything.’”
—Willard Van Orman Quine (b. 1908)