Exhaustive search algorithm solving vertex cover of size $k$ in time $2^{k}n^{O(1)}$?

Question

In the wiki page of Vertex Cover, it is claimed that an exhaustive search algorithm can solve the problem(the decision version of vertex cover problem) in time $2^{k}n^{O(1)}$.

Intuitively, with a fixed parameter $k$, in the worst case, the exhaustive search needs to check whether every vertex subset of size $k$ is vertex cover. The number of vertex subset of size $k$ is $\dbinom{n}{k}$, and we have $\dbinom{n}{k}=O(n^{k})$. Meanwhile, the number of steps to check a vertex subset of size $k$ is $O(kn)$, since we only need to verify whether the number of edge connected to or contained in the vertex subset is $m$, where $m$ is the number of edge in the graph. Thus, the time complexity of the exhaustive search is $O(k n^{k+1})$.

Is there any problem with my above analysis? And how to get a exhaustive search algorithm of time complexity $2^{k}n^{O(1)}$?

Answer 1

The search with the running time of $2^kn^{O(1)}$ is a different one. Personally, I would not have chosen to call it an exhaustive search. Not that it is incorrect, but as the question shows it may be misleading.

The classic algorithm goes as follows:

1. If all edges are covered, succeed.
2. If you already have chosen $k$ vertices, fail.
3. Consider the first uncovered edge.
4. One of its endpoints must be in the vertex cover. This leads to two possibilities, on which you recurse. In each branch of the recursion, continue at 1.

The recursion has depth $k$ and branches binarily. Thus there are $2^k$ paths in the search tree. Each step can be processed in polynomial time.

[EDIT]

Success in Step 1 means that the current candidate set is indeed a vertex cover, so the algorithm may accept.

Failure in Step 2 means that the current candidate set cannot be extended to a vertex cover of size $k$, so the search must continue in another branch.

Also, thanks to chi for pointing out an ambiguity.

Answer 2

This is just a Hint :

Let me give you a different algorithm. Suppose vertices of the input graph $G$ are numbered from $v_1$ to $v_n$. Now assume you have a size $k+1$ solution set i.e. a vertex cover set. How much time it will take to compress the solution set of size $k+1$ to $k$ ( think ).

Algorithm :

1. Initially put $v_1,v_2,\cdots v_{k+1}$ into solution size.
2. Check is it possible to compress the above set of size $k+1$ to $k$ vertex cover
3. If yes then do it

Now how to check whether it is possible or not to compress the vertex cover of size $k+1$ to size $k$ is by brute forcing on set of size $k+1$. Try all $k+1\choose k$ subsets of vertex cover of size $k+1$ and check whether they are vertex cover or not.