How to determine the approximation factor for greedy vertex cover algorithm?

The algorithm iteratively picks the vertex with maximum degree and removes it and every incident edge of the vertex, until only vertices with degree of $$0$$ are left.

Formally:

$$\text{GreedyVertexCover}(G)$$:

$$C\leftarrow \emptyset$$

While $$(E\neq\emptyset)$$

$$\hspace{10pt}\text{Pick a vertex }v \text{ that has maximum degree}$$

$$\hspace{10pt}C\leftarrow C\cup \{v\}$$

$$\hspace{10pt}E=E\setminus\{e\in E:v\in e\}$$

$$\hspace{10pt}\text{Remove all vertices with degree 0}$$

$$\text{ Return } C$$

My idea of the upper bound (please correct me if wrong): let $$v_1, ..., v_n$$ be the removed vertices. Define the cost of removing a vertex $$v_i$$ to be $$c(v_i) = \cfrac{1}{\deg(v_i)}$$. At any iteration $$i$$, among the vertices of the complementary set $$\bar{C}$$, there must exists a vertex with cost of at most $$\cfrac{OPT}{n - i + 1}$$. Therefore the cost of constructing the set $$C$$ can be at most

$$\sum_{i = 1}^{n} \cfrac{OPT}{n - i + 1} = \mathcal{O}(\log n) \cdot OPT$$

• Your upper bound is correct, also you can check the analysis of the upper bound which presented in web.cs.hacettepe.edu.tr/~ozkahya/classes/cmp741/Reading/… .
– Jut
Jul 19 '21 at 2:54
• If my answer is useful, you can accept it:)
– Jut
Jul 19 '21 at 2:55
• What's your question? This is a question-and-answer site, so we require you to identify a specific question. I don't see a question here.
– D.W.
Jul 19 '21 at 5:26

The approximation factor can be $$\Omega(\log n)$$.
Consider a bipartite graph $$G$$ with a set $$S_L$$ with $$n$$ nodes on the left side. Also consider a collection of sets $$S_{R,1},S_{R,2},\dots,S_{R,n}$$ on the right side where each set $$S_{R,i}$$ has an edge to $$i$$ vertices in $$S_{L}$$ and no two vertices in $$S_{R,i}$$s have common edge . So $$\lfloor{\frac{n}{i}}\rfloor$$ in it. So the sum of size of $$S_{R,i}$$s $$\sum_{i=0}^n |S_{R,i}|=\Theta(n\log n).$$
After running GreedyVertexCover on this instance, it select all nodes on right side, but the optimal solution was to select all nodes in $$S_L$$.
Consequently, $$\frac{ALG(G)}{OPT(G)}=\frac{n\log n}{n}=\log n.$$ So the approximation factor of your algorithm is $$\Omega(\log n)$$.