Consider the following variation (let us call it Q) on the Vertex Cover problem: Given a Graph G and a number K, we are asked if there is a k-cover of G so that it is the minimum cover. My question is: How may one prove that Q can be reduced to the general Vertex Cover problem? And, more generally, what is the approach to solve such a reduction, from "is there a k..." to "is k the minimum/maximum?"? I have a hunch on the methodology but am not sure and would appreciate a wiser opinion than that of myself on the subject.
My hunch is the following: First of all, we take into consideration the following fact: if there is a k-1 cover of G, then we will surely have a k cover of G, just by adding a random node to the k-1 cover ( the cover property holds if we add nodes ). Thus, We can reformulate Q this way: Is there a k-cover of G, so that there is no (k-1)-cover of the graph? From this reformulation it is clear that an instance of Q reduces to 2 instances of the original decision version of the Vertex Cover.