Greedy algorithm for vertex cover
-
29-09-2020 - |
题
Given a graph $G(V, E)$, consider the following algorithm:
- Let $d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $d\geq 1$)
- Let $v$ be one of the vertices with degree equal to $d$
- Remove all vertices adjacent to $v$ and add them to the proposed vertex cover
- 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?
解决方案
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):
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.
其他提示
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.
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.