Algorithm $2$: AL$.$C:$-$B

Input: An undirected graph $G=(V,E)$ and a coest function $\{c(v)\}$ with $c(v)>0$ for all vinV.

Output: A vertex cover of $G$ with the minimum cost.

$\frac{?}{?}+S$ is the vertex cover ve ais to output.

Initialization: $S=$;

while $E0$ do

Select a node $v$ such that $r(v)$:$=c\frac{v}{|}{E}_v|$ gets minimized among all vinV. Break ties

arbitrarily.

Update ElarrE$-E_v,$SlarrS$\{v\},$VlarrV$-\{v\}.$

end

Return $S.$

In the following, we aim to analyze the performance of ALC$-$B$.$ Consider the instance below.

Figure $1$: An instance of unuecighted vertex cover problem for Question $1.$

For the graph shown in Figure $1$: $(1)$ We have a bipartite graph $G=(UV,E)$ such that

$i6$ and $V=\{v=j|1j14\}.$ For simplicity, we use i and $j$ to index uinU and vinV, respectively.

$(2)$ The cost $c(u)=c(v)=1$ for all uinU and vinV. $(3)$ The set of edges $E$ is constructed as follows. For

the first group of six nodes on $V,V_1=\{v|v=1,2,3,$dots,$6\},$ conect each with a node $u=v$; for the scond

group of $V,V_2=\{v|v=7,8,9\},$ connect each with two nodes in $U$ such that each $vin{V}_2$ has a disjoint set

of neighbors; similarly, for the third group, $V_3=\{v|v=10,11\},$ each is conaected to a disjoint set of three

nodes in $U.$ For $V_4,V_6,$ and $V_6,$ each group consists of one single node $v$ of $V,$ which is connected to the first

$4,5,6$ nodes of $U,$ respectively.

$(1)$ What is the cost of the output vertex cover when applying ALC:$-$B to the instanox as described above?

What is the cost of an optimal vertex cower? Note that there may be ties to break when rumaing ALC$-$B$,$

and different breaking$-$tie choics may lead to different resalts. By default, we evaluate the performance of

ALC:$-$B based on the worst poesible breaking$-$tie choios of ALC:$-$B$.(10$ Points$)$

$(2)$ Plewe analyze the performaner of ALC$-$B following the exact instructions given in Question $3.($Hint:

Thy to get some insights from ansters to $($t$).)(10$ Points$)$

$(3)($Extra Credits$)$ Suppoee we modify AL$.$C$-$B such that it breaks ties uniformly every time, if any, in

Step $(3).$ Does this strategy help in improving the approximation ratio of AL$.$G$-$B$?$ Please justify your answers.

$(10$ Points$)$