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 problem of the novelist who wishes to write about a man’s encounter with God is how he shall make the experience—which is both natural and supernatural—understandable, and credible, to his reader. In any age this would be a problem, but in our own, it is a well- nigh insurmountable one. Today’s audience is one in which religious feeling has become, if not atrophied, at least vaporous and sentimental.”
—Flannery O’Connor (1925–1964)