<p>Unfortunately, the algorithm can be arbitrarily bad.  In the following example, each vertex <span class="math-container">$u_i$</span> has <span class="math-container">$d$</span> disjoint neighbors, of which only four are drawn. The optimal solution is <span class="math-container">$\{u_1, \ldots, u_p, w_1, \ldots, w_d\}$</span>, while the greedy algorithm returns its complement.  The ratio is <span class="math-container">$\frac{d p}{p + d} \approx d$</span> with <span class="math-container">$p\to 0$</span>.<a href="https://i.sstatic.net/IkBFR.png" rel="noreferrer"><img src="https://i.sstatic.net/IkBFR.png" alt="example"></a></p>

CC BY-SA 4.0
2021-03-02T13:28:04.147Z
I am sorry, why do you say $\frac{dp}{p+d} \approx  d$ with $p\rightarrow 0$? In my opinion it is $\frac{dp}{p+d} \approx  1$ with $p\rightarrow 0$ ($p\in \aleph$ and $p\geq 1$) and $d\gg p$.
Mario Giambarioli
CC BY-SA 4.0
2020-02-09T10:42:15.107Z
2020-02-09T10:42:15.107Z
Yixin Cao
<p>For the vertex cover problem (Given a graph <span class="math-container">$G$</span>, find a minimum set <span class="math-container">$S$</span> of vertices such that <span class="math-container">$G - S$</span> is edgeless), there are two famous greedy algorithms.  The edge greedy (finding an edge and taking its both ends) has ratio 2, while the maximum-degree greedy (taking a vertex with the maximum degree) has ratio O(log n). How about the following one:</p>

<ul>
<li>Repeat until the graph is edgeless,</li>
<li>take a vertex <span class="math-container">$v$</span> with the minimum degree, add <span class="math-container">$N(v)$</span> into the solution, and <span class="math-container">$G \leftarrow G - N[v]$</span>.</li>
</ul>

<p>I noticed some experiments on this algorithm (e.g., <a href="https://doi.org/10.1109/ICPCI.2012.6486444" rel="nofollow noreferrer">https://doi.org/10.1109/ICPCI.2012.6486444</a>). But my interest is on rigorous analyses. Is there any known ratio for it?</p>

<p>Any suggestion of bad examples for this algorithm is also very appreciated.</p>

<reference-request><approximation-algorithms><greedy-algorithms>
Is this greedy algorithm for vertex cover studied before?
Yixin Cao
# Is this greedy algorithm for vertex cover studied before?

(Asked by: username_0 on 2020-02-09)

For the vertex cover problem (Given a graph $G$, find a minimum set $S$ of vertices such that $G - S$ is edgeless), there are two famous greedy algorithms. The edge greedy (finding an edge and taking its both ends) has ratio 2, while the maximum-degree greedy (taking a vertex with the maximum degree) has ratio O(log n). How about the following one:

* Repeat until the graph is edgeless,
* take a vertex $v$ with the minimum degree, add $N(v)$ into the solution, and $G \leftarrow G - N[v]$.

I noticed some experiments on this algorithm (e.g., <https://doi.org/10.1109/ICPCI.2012.6486444>). But my interest is on rigorous analyses. Is there any known ratio for it?

Any suggestion of bad examples for this algorithm is also very appreciated.

**Tags:** reference-request, approximation-algorithms, greedy-algorithms

---

## 1 answers

### Answer by username_0 on 2020-02-09. Score: 5 | Accepted answer

Unfortunately, the algorithm can be arbitrarily bad. In the following example, each vertex $u\_i$ has $d$ disjoint neighbors, of which only four are drawn. The optimal solution is $\{u\_1, \ldots, u\_p, w\_1, \ldots, w\_d\}$, while the greedy algorithm returns its complement. The ratio is $\frac{d p}{p + d} \approx d$ with $p\to 0$.[![example](https://i.sstatic.net/IkBFR.png)](https://i.sstatic.net/IkBFR.png)

> **Comments:**
> **username_1**: I am sorry, why do you say $\frac{dp}{p+d} \approx  d$ with $p\rightarrow 0$? In my opinion it is $\frac{dp}{p+d} \approx  1$ with $p\rightarrow 0$ ($p\in \aleph$ and $p\geq 1$) and $d\gg p$.  

---

