Apply the Best-Possible Ordering for Solving a Decision Problem Your task In the Induced Subgraph Isomorphism problem,

you are given two graphs G1 = (V1, E1) and G2 = (V2, E2) and you are asked whether G1 is isomorphic to an induced subgraph of G2. In other words, is there a 1-1 mapping f : V1 −→ V2 such that each vertex of G1 is mapped to a vertex of G2 and for each pair of vertices u, v ∈ V1: (u, v) ∈ E1 ⇐⇒ (f(u), f(v)) ∈ E2.

1. Formulate the above as a CSP (hint: note that f “assigns” to each vertex of G1 an image in G2.

2. What happens to the neighbors and non-neighbors of vertices v ∈ V1 and v ∈ V2 if v is assigned as image of v? What kind of refinement can you apply and how would you implement it?

3. How would you solve the problem via recursive backtracking? (In other words, describe the search states, actions and give a high-level pseudocode of the backtracking algorithm).

4. What order would you choose for selecting a next vertex to branch on (or assign a value for)?

5. What order would you choose for assigning a vertex of G2 to a given vertex of G1?

6. What is the time complexity of your algorithm? Do you expect it to work well in practice?