0
$\begingroup$

Given a graph $G(V, E)$, consider the following algorithm:

  1. Let $d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $d\geq 1$)
  2. Let $v$ be one of the vertices with degree equal to $d$
  3. Remove all vertices adjacent to $v$ and add them to the proposed vertex cover
  4. Repeat from step 1. until in $G$ there are only vertices with degree $0$ (no edges in the graph)

At the end the removed vertices are a vertex cover of the given $G(V, E)$, but is it a minimum vertex cover? Is there an example where the algorithm does not find a minimum vertex cover?

$\endgroup$
  • $\begingroup$ I can say without checking that it doesn't always find a vertex cover (otherwise this algorithm would be found long ago). What's the motivation for your question? $\endgroup$ – Dmitry Aug 6 at 15:11
  • 6
    $\begingroup$ "doesn't always find a vertex cover" -> "doesn't always find a minimum vertex cover". I personally find this question rather strange (and a bit annoying): you come up with random heuristics, and of course it won't work for an NP-hard problem. While others may feel that it's a nice exercise to find a counterexample for a specific algorithm, I don't understand why you ask this question at all, also without showing any attempt (given that it should be simple to find a counterexample). $\endgroup$ – Dmitry Aug 6 at 15:25
4
$\begingroup$

Take $k$ copies of $C_4$, and attach them all to a single vertex. For instance, if $k=2$, you get the graph $X_{27}$ shown below (courtesy of graphclasses.org):

enter image description here

A vertex cover of size $k+1$ can be obtained by selecting the vertex with maximum degree (let's call it $w$) and all vertices that are not adjacent to it.

The algorithm you propose might start with one of the vertices of degree 2 that are not adjacent to $w$ (say, $v$) and will add both neighbours to the cover, and then we repeat the process on the rest of the graph. In the case where $k=2$ above, you will end up with a cover of size $4$, whereas what I described in the previous paragraph yields a cover of size 3.

Side note: as counter-intuitive as this algorithm seems (in the sense that if I had to be greedy with respect to the degree, I'd naturally extract a maximum degree vertex at every iteration), it seems to have been proposed before. See this question on cstheory.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is easily overcome by starting at all vertices of minimal degree, right? It's easy to adapt the algorithm to solve this, so I don't think it is a very strong counterexample. $\endgroup$ – cangrejo Aug 17 at 10:00
4
$\begingroup$

Start with a clique on the vertices $A,B,C,D$.

Connect $A,B$ to a new vertex $a$.

Connect $B,C$ to a new vertex $c$.

Connect $a,c$ to a new vertex $b$.

The vertex $b$ is the only one of degree 2, so your algorithm will start by adding $a,c$ to the vertex cover. The remaining graph consists of the clique $A,B,C,D$ and the isolated vertex $b$, so the algorithm will add 3 more vertices, ending up with a vertex cover of size 5.

In contrast, the 4 vertices $A,B,C,b$ cover all edges.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why would the algorithm "add $3$ more vertices"? I see that it will add only $2$. The isolated vertex is not taken into account by the algorithm as step 1 only considers vertices with degree at least 1. $\endgroup$ – Bernardo Subercaseaux Aug 6 at 16:19
  • 1
    $\begingroup$ It will choose, say $A$, and add its three neighbors $B,C,D$. This is actually optimal – you need three vertices to cover all edges of the clique. $\endgroup$ – Yuval Filmus Aug 6 at 20:12
  • $\begingroup$ you're right, thanks! $\endgroup$ – Bernardo Subercaseaux Aug 6 at 22:19
3
$\begingroup$

counterexample

Using the notation $[v](n_1,\ldots,n_k)$ to mean that because of vertex $v$ we remove its neighbors $n_1$ through $n_k$, your algorithm might remove vertices in the following way: $[2](1,5,7), [6](8), [3](9,11), [10](12), [4](13,15), [14](16)$. This yields a vertex cover of size $10$.

However, $(2,6,8,3,10,12,4,14,16)$ is a vertex cover of size 9.

| cite | improve this answer | |
$\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.