What is a quick and a elegant way to reduce vertex cover to minimal vertex cover?

Is it possible to use vertex cover as verifier in the algorithm that reduces vertex cover to minimal vertex cover? since minimal vertex cover is essentially $min{f(x)|x\in VertexCover(G)}$

Graph is basic if it matters, no weights, and it is undirected

thank you for helping


1 Answer 1


Search for Bellare and Goldwasser "The Complexity of Decision vs. Search" SIAM J. of Computing 23:1 (Feb 1994), pp. 97-119, or Bellare's class note on the matter.


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.