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?


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.

  • $\begingroup$ Thanks! I haven't done graph theory in a while, and this question came up whilst talking about it with an undergrad friend of mine. $\endgroup$ – Gabriel_s_syme Nov 13 '14 at 13:21

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.