Consider the following problem: given an undirected graph G = (V, E), find a smallest subset of vertices S with the property that for every vertex v elementof V, |N_v intersection S| greaterthanorequalto 1, where N_v = {v} union {u: (u, v) elementof E}. (a) Formulate the above problem using an integer linear program (ILP). (b) Give the fractional linear program corresponding to the above ILP and show that it is not integral, i.e., give an example demonstrating an integrality gap greater than 1 for this LP. (c) Write the dual of this LP. (d) Write the ILP corresponding to this dual LP and state the problem it represents in words. (e) Show that this dual LP is also not integral, i.e., give an example demonstrating an integrality gap greater than 1 for the dual LP