Vertex cover is optimization problem. Given an input graph , find out the smallest number such that has vertex cover of size .
The vertex cover is also a decision problem. Given input and and integer , find out if has vertex cover of size at most .
Minimum vertex cover can be formulated as an optimization problem.