4. NP: (30%) The SET-cover problem is defined as follows: Given a set U of elements, a collection S of subsets of U, and an integer k, are there k of these subsets whose union is equal to U ? A reduction from Vertex cover is as follows: Given a graph G=(V,E) and k, we construct a SET-COVER instance (U,S,k) that has a set cover of size k iff G has a vertex cover of size k. Universe U=E, and we include one subset for each node vV:Sv={eE: e incident to v}. See example below. U={1,2,3,4,5,6,7}Sa={3,7}Sc={3,4,5,6}Se={1}k=2 Sb={2,4} Sd={5} Sf={1,2,6,7} (a) (8%) Show that SET-Cover is in NP. (b) (8%) Show that the reduction is polynomial. (c) (10%) Show that the graph G has a vertex cover of size k iff U has a set cover of size k. Don't forget the two directions. (d) (4%) What are the set cover and the vertex cover in the figure above