2
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ All problems on vertex cover are not equal. $\endgroup$
    – John L.
    Dec 14 '21 at 3:01
4
$\begingroup$

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.

$\endgroup$

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.