Given a graph G-(V E), an independent set ?s a set of vertices V, such that V,-V and no two vertices in V' are connected by an edge in E. The problem of determining the maximum-size independent set in a graph is known to be NP-complete. Here is the decision version of that problem: IS (G, k) G is an undirected graph with an independent set of size k) In this question, we investigate two related problems. (Be sure to turn the page for the second part!) (a) Suppose that G is a tree. Consider the following special case of the INDSET problem: IST-G, k)G is an undirected tree with an independent set of size k) Show that IST P (b) Now consider the following variant of the problem of finding the independent set in a general undirected graph. Specialis = {(G,k.u [Gish at undirected graph with an independent set ofsizek includes vertexv Show that SpeciallS is NP-complete. Given a graph G-(V E), an independent set ?s a set of vertices V, such that V,-V and no two vertices in V' are connected by an edge in E. The problem of determining the maximum-size independent set in a graph is known to be NP-complete. Here is the decision version of that problem: IS (G, k) G is an undirected graph with an independent set of size k) In this question, we investigate two related problems. (Be sure to turn the page for the second part!) (a) Suppose that G is a tree. Consider the following special case of the INDSET problem: IST-G, k)G is an undirected tree with an independent set of size k) Show that IST P (b) Now consider the following variant of the problem of finding the independent set in a general undirected graph. Specialis = {(G,k.u [Gish at undirected graph with an independent set ofsizek includes vertexv Show that SpeciallS is NP-complete