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

i $<=6\}$ and V $=\{$v $=$ j $|1<=$ j $<=14\}.$ 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$.$