need typed answer do anyone your wish

dont provide code need algorithm

2. A dominating set of a graph is a subset D of vertices such that every vertex that is not in D is adjacent to some vertex in D. The input to the DominatingSet problem is a graph G and an integer k, and the output is whether G has a dominating set of size at most k. Prove that the following procedure is a Karp reduction from VertexCover to DominatingSet. VCtoDS(G, k): 1. Construct a vertex set V' by taking the vertex set V of G, and then adding a vertex ve for each edge e of G 2. Construct an edge set E' as follows. For each edge e = (a,b) of G, add three edges - (a, ve), (6,ve), and (a, b) to El. 3. Return the instance (G', k) of DominatingSet, where G' = = (V', E'). Hint: Using an exchange argument, prove that G' has a minimum size dominating set which doesn't contain any of the vertices ve EVV. 3. Let U be a finite set and, like in the Set Cover problem, let S C 20 be a collection of subsets of U. We say that a set H CU is a hitting set of S if for all A E S, we have H NA # , or in other words, H intersects every set in S. In the HittingSet problem, we are given U, S C 20, and an integer k as input. We are required to determine whether there is a hitting set of S having size at most k. Design a Karp reduction from VertexCover to HittingSet. (2 denotes the powerset of U, that is, the collection of all subsets of U.) 4. Recall that two graphs G = (V, E) and G' = (V', E') are called isomorphic if there exists a bijection h:V V' such that for all vertices u, v EV, (u, v) E if and only if (f(u), f(v) E E, and such a bijection is called an isomorphism between G and G'. In other words, an isomorphism is an adjacency- preserving bijection. Also recall that a subgraph of a graph G is any graph that is obtained by deleting some vertices and edges of G. a In the SubgraphIsomorphism problem, the input consists of two graphs, say G and G', and we are required to determine whether G' is isomorphic to some subgraph of G. Recall the Clique problem discussed in class, in which the input is a graph G and an integer k, and we are required to determine whether G contains k vertices that are pairwise neighbors. Design a Karp reduction from Clique to SubgraphIsomorphism. b In the Graph Isomorphism problem, the input consists of two graphs, say G and G', and we are required to determine whether G and G' are isomorphic. Prove that GraphIsomorphism is in NP by designing a polynomial-time verifier for GraphIsomorphism. 2. A dominating set of a graph is a subset D of vertices such that every vertex that is not in D is adjacent to some vertex in D. The input to the DominatingSet problem is a graph G and an integer k, and the output is whether G has a dominating set of size at most k. Prove that the following procedure is a Karp reduction from VertexCover to DominatingSet. VCtoDS(G, k): 1. Construct a vertex set V' by taking the vertex set V of G, and then adding a vertex ve for each edge e of G 2. Construct an edge set E' as follows. For each edge e = (a,b) of G, add three edges - (a, ve), (6,ve), and (a, b) to El. 3. Return the instance (G', k) of DominatingSet, where G' = = (V', E'). Hint: Using an exchange argument, prove that G' has a minimum size dominating set which doesn't contain any of the vertices ve EVV. 3. Let U be a finite set and, like in the Set Cover problem, let S C 20 be a collection of subsets of U. We say that a set H CU is a hitting set of S if for all A E S, we have H NA # , or in other words, H intersects every set in S. In the HittingSet problem, we are given U, S C 20, and an integer k as input. We are required to determine whether there is a hitting set of S having size at most k. Design a Karp reduction from VertexCover to HittingSet. (2 denotes the powerset of U, that is, the collection of all subsets of U.) 4. Recall that two graphs G = (V, E) and G' = (V', E') are called isomorphic if there exists a bijection h:V V' such that for all vertices u, v EV, (u, v) E if and only if (f(u), f(v) E E, and such a bijection is called an isomorphism between G and G'. In other words, an isomorphism is an adjacency- preserving bijection. Also recall that a subgraph of a graph G is any graph that is obtained by deleting some vertices and edges of G. a In the SubgraphIsomorphism problem, the input consists of two graphs, say G and G', and we are required to determine whether G' is isomorphic to some subgraph of G. Recall the Clique problem discussed in class, in which the input is a graph G and an integer k, and we are required to determine whether G contains k vertices that are pairwise neighbors. Design a Karp reduction from Clique to SubgraphIsomorphism. b In the Graph Isomorphism problem, the input consists of two graphs, say G and G', and we are required to determine whether G and G' are isomorphic. Prove that GraphIsomorphism is in NP by designing a polynomial-time verifier for GraphIsomorphism