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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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