Why minimum vertex cover problem is in NP

Question

I am referring to the definition of the minimum vertex cover problem from the book Approximation Algorithms by Vijay V. Vazirani (page 23):

Is the size of the minimum vertex cover in $G$ at most $k$?

and right after this definition, the author states that this problem is in NP.

My question: What would be a yes certificate?

Indeed, our non-deterministic algorithm could guess a subset of vertices, denoted by $V'$, and we can verify if $V'$ is a vertex cover of some cardinality in polynomial time, but how could we possibly show that $V'$ is minimum in polynomial time?

Answer 1

You don't have to verify that $V'$ is minimum. The decision version of Vertex Cover (which you have quoted in your question) only asks you to decide whether there is a vertex cover of size at most $k$.

To verify that $V'$ is a valid yes-certificate for an instance $\langle G=(V,E), k \rangle$ you just check that:

• $V' \subseteq V$,
• $|V'| \le k$, and
• $\forall (u,v) \in E, \{u,v\} \cap V' \neq \emptyset$.