The subgraph-isomorphism problem takes two undirected graphs G1 and G2, and it asks whether G1 is isomorphic (structurally identical) to a subgraph of G2. Show that the subgraph-isomorphism problem is NP-complete.
(1) Give an example of two undirected graphs G1 with nodes {Miami, FIU, SCIS, your Family Name} and G2 with nodes {MS, COT5407, Fall, 2021, Final}, you can choose your own edges as long as you can give a mapping to show the subgraph- isomorphism;
(2) Argue that the subgraph-isomorphism problem is in NP, i.e. describing how to check that G1 is isomorphic to a subgraph of G2 in polynomial time (note: this is for general G1 and G2, not for the above example);
(3) Prove that the subgraph-isomorphism problem is NP hard using the reduction technique, i.e. find a known NP-complete problem ????≤p Sub −????so (hint: use Clique). Make sure to give the following details:
(a) Describe an algorithm to compute a function ???? mapping every instance of ???? to an instance of Sub −????so;
(b) Prove that x∈???? if and only if ????(x)∈Sub −????so;
(c) Show that ???? runs in polynomial time.
