# Why minimum vertex cover problem is in NP

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?

• Please do not delete your question when you have received an answer that solves your problem. We want to keep answered questions around to not only help you, but also future readers. Instead, you can indicate whether an answer is useful for you (or not) by voting, or by accepting the answer that helped you the most. – Discrete lizard Jun 23 '20 at 17:10

## 1 Answer

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$$.