Proving NP-completeness by generalization. For each of the problems below, prove that it is NP-complete by showing that it is a generalization of some NP-complete problem we have seen in this chapter (a) SUBGRAPH ISOMORPHISM: Given as input two undirected graphs G and H, determine whether Gis a subgraph of H (that is, whether by deleting certain vertices and edges of H we obtain a graph that is, up to renaming of vertices, identical to G), and if so, return the corresponding mapping of V (G) into V(H). (b) LONGEST PATH: Given a graph G and an integer g, find in G a simple path of length g. (C) MAX SAT: Given a CNF formula and an integer g, find a truth assignment that satisfies at least g clauses. (d) DENSE SUBGRAPH: Given a graph and two integers a and b, find a set of a vertices of G such that there are at least b edges between them. (e) SPARSE SUBGRAPH: Given a graph and two integers a and b, find a set of a vertices of G such that there are at most b edges between them. (G) into V(H). (b) LONGEST PATH: Given a graph G and an integer g, find in G a simple path of length g. (c) MAX SAT: Given a CNF formula and an integer g, find a truth assignment that satisfies at least g clauses. (d) DENSE SUBGRAPH: Given a graph and two integers a and b, find a set of a vertices of G such that there are at least b edges between them. (e) SPARSE SUBGRAPH: Given a graph and two integers a and b, find a set of a vertices of G such that there are at most b edges between them. (f) SET COVER. (This problem generalizes two known NP-complete problems.) (g) RELIABLE NETWORK: We are given two nx n matrices, a distance matrix dij and a connectivity requirement matrix rij, as well as a budget b; we must find a graph G = ((1, 2,...,n}, E) such that (1) the total cost of all edges is bor less and (2) between any two distinct vertices i and j there are rij vertex- disjoint paths. (Hint: Suppose that all dij are 1 or 2, b = n, and all rij's are 2. Which well known NP-complete problem is this?)