In the Greedy

$-$

Algorithm lecture one of the exercises considered the following greedy heuristic for

finding a minimum vertex cover. At each step, select the vertex v from Gi having highest degree and

add v to the cover. Then Gi

$+$

$1$

$$is obtained from Gi by removing v and any edge incident with v

$.$

Consider the wheel graph Wn which has vertex set V $=\{$c$,$ p$1,$ p$2,...,$ p$2$n$1,$ p$2$n$\},$ and edge

set E $=$ Eperim $\backslash$cup Espoke where Eperim $=\{($p$1,$ p$2),($p$2,$ p$3),...,($p$2$n$1,$ p$2$n$),($p$2$n$,$ p$1)\}$ and

Espoke $=\{($c$,$ p$1),($c$,$ p$3),...,($c$,$ p$2$n$1)\}.$

$($a$)$ For the Vertex Cover approximation algorithm presented in lecture, determine the resulting

cover and approximation ratio when the algorithm is applied to Wn and the edges are

presented to the algorithm as

$($c$,$ p$1),($c$,$ p$3),...,($c$,$ p$2$n$1),($p$1,$ p$2),($p$2,$ p$3),...,($p$2$n$1,$ p$2$n$).$

Explain your reasoning.

$($b$)$ Repeat the previous problem but now assume the algorithm being used is the greedy

algorithm desc