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 $34$ In the class, we have discussed a Greedy$-$Based algorithm for weighted Vertex Cover Problem

$($VCP$).$ Below is a formal statement.

$2$

Algorithm $2$: ALG$-$B

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

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

$/*$ S is the vertex cover we aim to output. $*/$

$1$ Initialization: S $=$;

$2$ while E $6=$ do

$3$ Select a node v such that $\backslash$tau $($v$)$ :$=$ c$($v$)/|$Ev $|$ gets minimized among all v in V $.$ Break ties

arbitrarily.

$4$ Update E $$ E $$ Ev $,$ S $$ S $\backslash$cup $\{$v$\},$ V $$ V $\{$v$\}.$

$5$ end

$6$ Return S$.$

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

u $=1$ u $=2$ u $=3$ u $=4$ u $=5$ u $=6$

v $=1234567891011121314$

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

For the graph shown in Figure $1$: $(1)$ We have a bipartite graph G $=($U $\backslash$cup V$,$ E$)$ such that U $=\{$u $=$ i

i and V $=\{$v $=$ j j For simplicity, we use i and j to index u in U and v in V $,$ respectively.

$(2)$ The cost c$($u$)=$ c$($v$)=1$ for all u in U and v in V $.(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,...,6\},$ connect each with a node u $=$ v; for the second

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

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

nodes in U $.$ For V$4,$ V$5,$ 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 ALG$-$B to the instance as described above?

What is the cost of an optimal vertex cover? Note that there may be ties to break when running ALG$-$B$,$

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

ALG$-$B based on the worst possible breaking$-$tie choices of ALG$-$B$.$