# How are these problem variants that ask about the size of optimal solutions in NP?

I just started reading Vazirani's book "Approximation Algorithms". It is legally available online here.

On page 5 (23 in the pdf), it says that the following decision problems are in NP:

• Is the size of the minimum vertex cover in $G$ at most $k$?
• Is the size of the maximum matching in $G$ at least $l$?

I can't see why this is true. If, say, the first problem is in NP, then each valid instance (graph) has a Yes certificate which proves that the graph has a minimum vertex cover of size at most $k$.

But, how can one deduce from a certificate something regarding the size of the minimum vertex cover?

• This book is still on my todo list, but I have to comment you probably will want an (lower level) book on optimization as reference as it seems to assume you're comfortable with non-approximation algorithms already. You might want to take a look at this freely available pdf by Alexander Schrijver: homepages.cwi.nl/~lex/files/dict.pdf Chapter 6 covers some of the main concepts in the introduction of Vazirani a more accesable way I think. – Thomas Bosman Aug 17 '15 at 21:49

Any vertex cover of size $k$ is a witness that the smallest one has at most size $k$. Hence, the questions
Is there a vertex cover of size at most $k$?
Does a smallest vertex have size at most $k$?