# find vertex cover of size at most 30 of a graph

This is a question from an exam I got wrong. Given an undirected graph $$G$$. Consider the decision problem of finding if there exists a vertex cover of size at most 30. Can we find a polynomial time algorithm for this problem? I answered that it is not possible because vertex cover is NP hard, but it turns out that there is a polynomial time algorithm. What is the reasoning behind this?

• All problems on vertex cover are not equal. Dec 14, 2021 at 3:01

Be careful about constants! There is a huge difference between the problem $$\text{On input } G, n, \text{ does there exist a vertex cover of size at most } n?$$ and $$\text{On input } G, \text{ does there exist a vertex cover of size at most 30}?$$
Notice, in particular, that the first problem has two inputs, $$G$$ and $$n$$. The second problem only has one input, $$G$$.
The first problem is NP-hard because it is very hard to find vertex covers. But the second problem should look intuitively much easier (when put in this form, where you see that $$n$$ is not part of the input) -- because we don't have to look for an arbitrary vertex cover, and instead we only have to look for a vertex cover of size at most 30. How does that help us?
Well, how many vertex covers are there of size at most 30? If $$|V|$$ is the number of vertices in the graph, then there are at most $$|V|^{30}$$ vertex covers. That's a big number, but $$30$$ is a constant -- so it's a polynomial in $$|V|$$ -- that is, it's polynomially many vertex covers that we have to check.
Therefore, this problem is in $$P$$, and the algorithm is as follows: check all lists of $$30$$ vertices -- of these lists there are only polynomially many, and they can be enumerated explicitly. For each of these $$|V|^{30}$$ lists, check if the list is a vertex cover (take a moment to think about how we would check that a given list is a vertex cover or not). Then finally, if any of them is a vertex cover, accept; otherwise, if none of them is a vertex cover, reject.