2. Let G = (V,E) be an undirected graph. A vertex cover of G is a subset U of V such that every edge in E is incident to at least one vertex in U. A minimum vertex cover is one with the lowest number of vertices. For example {1,3,5,6} and {2,3,5} are both vertex covers for the graph below, with the latter being a minimum vertex cover. Consider the following greedy algorithm for the minimum vertex cover problem: algorithm VERTEXCOVER(G = (V,E)): while E 0 do Find a vertex v of maximum degree UUU {v} V← V\{v} EE\{(x, y) = E : x = v V y = v} return u 5 4 3 (a) Refine the algorithm above by providing detailed descriptions of all the steps using suitable data structures. Justify your choice of data structure and determine the overall running time. (b) Give an example (other than the graph above) where this algorithm returns a minimum vertex cover. (c) Give an example (other than the graph above) where this algorithm does not return a minimum vertex cover. (d) How far from the minimum vertex cover do you think the vertex cover produced by this algorithm is in the worst case? You do not have to provide a proof or tight argument, but you need to offer some justification.

2. Let G = (V,E) be an undirected graph. A vertex cover of G is a subset U of V such that every edge in E is incident to at least one vertex in U. A minimum vertex cover is one with the lowest number of vertices. For example {1,3,5,6} and {2,3,5} are both vertex covers for the graph below, with the latter being a minimum vertex cover. Consider the following greedy algorithm for the minimum vertex cover problem: algorithm VERTEXCOVER(G = (V,E)): while E 0 do Find a vertex v of maximum degree UUU {v} V← V\{v} EE\{(x, y) = E : x = v V y = v} return u 5 4 3 (a) Refine the algorithm above by providing detailed descriptions of all the steps using suitable data structures. Justify your choice of data structure and determine the overall running time. (b) Give an example (other than the graph above) where this algorithm returns a minimum vertex cover. (c) Give an example (other than the graph above) where this algorithm does not return a minimum vertex cover. (d) How far from the minimum vertex cover do you think the vertex cover produced by this algorithm is in the worst case? You do not have to provide a proof or tight argument, but you need to offer some justification.