Vertex Cover

Vertex cover is optimization problem. Given an input graph $G = (V, E)$, find out the smallest number $k$ such that $G$ has vertex cover of size $k$.

The vertex cover is also a decision problem. Given input $G$ and and integer $k$, find out if $G$ has vertex cover of size at most $k$.

Minimum vertex cover can be formulated as an optimization problem.

Figure: Vertex Cover: The (b) is optimal of (a) and (d) is optimal of (c).