1
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Discrete lizard ♦
    Commented Jun 23, 2020 at 17:10

1 Answer 1

Reset to default
2
$\begingroup$

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$.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.