t1=1, for i=1 to 9 Answer the following questions: (a) Show that the construction can be done in polynomial time. (b) Show that if the 3DM problem instance is a yes-instance, then the constructed instance of the intersection numbers problem is also a yes-instance. Question 2 (4 Marks) Referring to Question 1, answer the following questions: (a) Show that the intersection numbers problem is in NP. (b) Show that if the constructed instance of the intersection numbers problem is a yes-instance, then the 3DM instance (used to construct the intersection numbers problem instance) is a yes-instance. Question 3 (4 Marks) Consider the following algorithm for the vertex cover (optimization) problem for an input graph G=(V,E) : 1. Construct a rooted tree T by performing a depth-first traversal of G. The tree T is built by adding an edge into the tree at the time the edge is traversed in G. The tree is known as a depth-first tree. An example is given at the end of the question. 2. Let S be the set of non-leaf vertices of the depth-first tree T. 3. Return S Answer the following questions: (a) Prove that S is a vertex cover of G. (b) Suppose M be a maximal matching of G where SV(M). Note that such a maximal matching can be obtained during the depth-first search process but you don't need to know or show how this is done. Given the maximal matching M, prove that the algorithm is a 2-approximation algorithm for the vertex cover problem. Note: V(M) is the set of endpoints of the edges in M. In Figure 1, the graph on the left is the graph we are doing a depth-first traversal of. The trees in the middle and right are two possible trees constructed from a depth-first traversal of G, starting at vertex 2. The numbers in red denote the ordering in which the edges are traversed and added to the tree. For more information on depth first traversal, sce link