4. (6 points) Show the following problem is NP-complete. MAXIMUM CoMMOn SUBGRAPH Input: Two grpahs G1-(Vi, Ei) and G2 (V2, E2); a budget b. Output: Two sets of nodes VI S Vi and Vi S V2 whose deletion leaves at least b nodes in each graph, and makes the two graphs identical (Strictly speaking, when we say two graphs Gi-?,E) and G,-(VyE2) are identical, we mean they are isomorphic, i.e., there exists a one-to-one correspondance : Vi ? , such that (u, u) E E ? (o(u), (v)) ? E2. It is worth noting that given two graphs, determining whether they are isomorphic to each other is not an easy problem - no polynomial time algorithm is known; however, it is also highly unlikely that this decision problem is NP- complete_highly unlikely in the sense that some widely believed complexity hypothesis, albeit stronger than P NP, would break if the problem were NP-complete.)