Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
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.
