Now I want to solve the following problem :

Question 5. [20 Marks] In class, we saw the following greedy algorithm for the Minimum Vertex Cover problem, and noted that it is an O(log n)-approximation algorithm, meaning its output may be at most O (log n) times the size of a minimum vertex cover. In particular, it is not a 2-approximation. . Input. G = (V, E) . set U = 0 . while E / 0 . choose a to be the vertex with the largest degree . U = UU{} . delete all edges incident to v from E . return U In this problem we consider a variation of the above algorithm. The new algorithm will track a slightly more sophisticated cost c() for each vertex, and instead choose the vertex with minimum cost at each iteration. . Input. G = (V, E) set c(u) = 1 for each u E V . set d(u) = (v E V : w e E)| . set U = 0 . while E / 0 . choose a to be the vertex with c()/d(v) minimized . U = UU{v} . for each u E V such that wv e E: . c(u) = c(u) - (c(v)/d(v)) . d(u) = d(u) - 1 3 . delete up from E . return We now prove that the above variation is a 2-approximation for Minimum Vertex Cover. Let G be any graph, let ( be the set of vertices output by the algorithm, and let c(v), d() be the values of c and d for the vertex v when the algorithm terminates. Finally, for each edge e = wv E E, let c(uv) = c(w)/d(w) where w E {u, v) is the first endpoint of the edge wv that was added to U by the algorithm. 1. [5 Marks] Prove that when the algorithm terminates, c(u) 2 0 for all u e V. 2. [5 Marks] Prove that when the algorithm terminates, for every vertex u E V, [ c(up) $ 1, 3. [5 Marks] Prove that when the algorithm terminates, for every vertex u E U, E c(up) = 1. 4. [5 Marks] Combine parts (1), (2), and (3) to prove that this algorithm is a 2- approximation. To do this, prove where | | is any minimum vertex cover on G