1
$\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?

Improve this question
$\endgroup$
2
  • $\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$ Commented Aug 6, 2020 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$ Commented Aug 6, 2020 at 15:25

3 Answers 3

Reset to default
6
$\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.

Improve this answer
$\endgroup$
2
  • $\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$ Commented Aug 6, 2020 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$ Commented Aug 6, 2020 at 20:12
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.

Improve this answer
$\endgroup$
1
  • $\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$ Commented Aug 17, 2020 at 10:00
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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.