As most of you know, the problem of finding a minimal vertex cover for an arbitrary graph is an NP-hard problem. I was wondering, if there existed a non-constructive way of calculating the size of a minimal vertex cover. That is, if you find a minimal vertex cover, this tells you the minimum size of a vertex cover. However, what if you know that the size of a minimal vertex cover is m, does this help you find such a covering?
My back of the envelope calculation tells me that, on a graph with n vertices, if you know that the size of a minimal vertex cover is m, you just need to check all subsets of V (the set of verticies) of size m, that is ${n \choose m} $. As a function of n, this has growth $O(n^n)$ i.e. not polynomial. So naively you don't get a polynomial reduction, and so the problem doesn't appear to be NP-hard.
So is finding the minimum size of a vertex cover an easier problem than finding a minimal vertex cover?
Best Answer
Actually, the classical NP-complete "vertex cover" problem is the decision problem: given natural number $k$ and graph $G$, is there a vertex cover of size $\le k$?
If you could solve this problem in polynomial time, you could also find a cover of minimal size in polynomial time. The point is that given a vertex $v$, there is a vertex cover of size $k$ that contains $v$ iff the graph $G'$ obtained from $G$ by removing $v$ and its incident edges has a vertex cover of size $k-1$. So you pick a vertex and test whether $G'$ has such a cover. If the answer is yes, you place $v$ on your list and look at $G'$. If the answer is no, then place all neighbours of $v$ on your list (as they are needed to cover the edges incident on $v$), remove $v$, its neighbours, and the edges incident on them, and look at the resulting graph.