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.