vertex cover problem

In computer science, the vertex cover problem or node cover problem is an NP-complete problem in complexity theory, and was one of Karp's 21 NP-complete problems. A vertex cover of an undirected graph  is a subset of the vertices of the graph which contains at least one of the two endpoints of each edge: . In the graph at the right, {1,3,5,6} is an example of a vertex cover. {2,4,5} is another, smaller vertex cover.The vertex cover problem is the optimization problem of finding a vertex cover of minimum size in a graph. The problem can also be stated as a decision problem:INSTANCE: A graph and a positive integer .QUESTION: Is there a vertex cover of size or less for ?
See more at Wikipedia.org...