2
$\begingroup$

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)}$?

$\endgroup$
  • 2
    $\begingroup$ There is no problem with your observation. The conclusion is that you need to do something smarter to arrive at a $2^k n^{O(1)}$-time algorithm. This is one of the most popular basic examples of FPT algorithms covered in many textbooks and sources. If you want a spoiler, you can just google for it. $\endgroup$ – Juho Jun 25 '18 at 11:03
  • $\begingroup$ I can find the largest connected component in a graph in polynomial time. However, your objection holds true there as well ... don't you have to look at every vertex subset, i.e. $2^n$ many of them to be sure you've found the biggest? $\endgroup$ – Pål GD Jun 25 '18 at 19:18
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does the failure of your algorithm necessarily mean that there exists no vertex cover of size $k$? $\endgroup$ – Mengfan Ma Jun 26 '18 at 7:33
  • $\begingroup$ A crucial point here is that step 3 is not a branching step. That is, we do not have to try all the uncovered edges, we can pick one greedily, and never consider other choices. This is in contrast with step 4 where we do use a non-deterministic choice / branching step. $\endgroup$ – chi Jun 26 '18 at 8:49
  • $\begingroup$ So the recurrence is $T(n,k)=2T(n-1,k-1)+O(n)$, which solves to $T(n,k)=O(2^{k}n)$. $\endgroup$ – Mengfan Ma Jun 26 '18 at 11:27
  • $\begingroup$ @Mark: I have added to the answer what failure of a branch means. Overall failure means that no branch led to a vertex cover. As the choice in Step 4 is exhaustive (with respect to the edge at hand), this implies that the input is a NO-instance. $\endgroup$ – kne Jun 26 '18 at 13:00
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks for answer!But I don't quite understand claim 1. A vertex of degree $\ge k$ is not necessarily in a vertex cover of size $k$. So what do you mean by it should be in the vertex cover? $\endgroup$ – Mengfan Ma Jun 25 '18 at 9:06
  • 1
    $\begingroup$ It most certainly is (for strictly greater as is written). Suppose a vertex $v$ has degree $k+1$ and you decide that $v$ shouldn't be in the vertex cover. Then what? $\endgroup$ – Pål GD Jun 25 '18 at 19:16
  • 1
    $\begingroup$ @old You don't need any preprocessing. You just pick any edge $uv$ and you know that either $u$ or $v$ needs to be in the vertex cover. So you branch. Branching factor is 2, depth is $k$. $\endgroup$ – Pål GD Jun 25 '18 at 19:20

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.