I have a graph problem that I would like to prove NP-completeness. It is outlined below:
A graph problem compromising of two graphs, say $G_1(V_1,E_1)$ and $G_2(V_2,E_2)$ such that $V_i$ and $E_i$ denote the nodes and edges respectively. An answer to the following question is required:
Does $\exists$ subset $V \subset V_2$ and one-to-one mapping $f:V_1 \to V \ni$ for any $v'\&v'' \in \{V_1\}$, the edge $[v',v'']\in E_1$ iff $[f(v'),f(v'')]\in E_2$?
I think reduction to a 3-sat problem should do the trick, however I have having troubles to actually execute the reduction. I tried out some examples and attempted to convert the graphs into 3-sat, didn't work out as expected. Any help is appreciated, thanks!
If you can use that the CLIQUE problem is NP-Complete, you can use the inclusion map to reduce from CLIQUE to SUBGRAPH-ISOMORPHISM. Here, the subgraph in question is the clique of the specified size.