0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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/… . $\endgroup$
    – Jut
    Jul 19 '21 at 2:54
  • $\begingroup$ If my answer is useful, you can accept it:) $\endgroup$
    – Jut
    Jul 19 '21 at 2:55
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jul 19 '21 at 5:26
2
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.