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

Question

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 $$

Answer 1

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)$.