[Solved]: Reduce variant of Vertex Cover to original decision-version Vertex cover problem

Problem Detail: 

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.

Asked By : Joseph A.

Answered By : David Richerby

Your reduction works. A more efficient version would be to use binary search to find the optimal value through a series of queries "Is there a vertex covers of size $k$?"

However, note that this is a polynomial-time Turing reduction (also known as a Cook reduction): you're solving the vertex cover optimization problem by making multiple queries to an oracle for the decision version. On the other hand, NP-completeness is defined in terms of polynomial-time many-one reductions (a.k.a. Karp reductions): here, you're only allowed to make one to the decision version. I'm not aware of a many-one reduction between these two problems.

Cook reductions have the advantage that they correspond more closely to the idea of "If I have an efficient algorithm for problem A and a reduction from B to A, I have an efficient algorithm for B, too. On the other hand, Karp reductions allow for finer-grained distinctions in complexity theory. For example, there are Cook reductions between NP-complete problems and coNP-complete problems but a Karp reduction between an NP-complete problem and a coNP-complete problem would prove that NP=coNP.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18997