I am considering the following problem:
Input: 3 graphs $G=(V,E)$, $H_1$, $H_2$
Question: Is there some $V_1\subseteq V$ such that $G[V_1]$ (the subgraph induced by $V_1$) is isomorphic to $H_1$, and $G[V\backslash V_1]$ is isomorphic to $H_2$?
It is clearly at least as hard as Graph Isomorphism (take the empty graph for $H_2$), and in NP (certificate: $V_1$ and the isomorphisms). Intuitively, it should be easier than subgraph isomorphism, since here we know what the "complement" looks like.
I have several questions regarding this:
- Has it been studied / does it have a name?
- If yes, is it NP-hard?
- If still yes, has it been studied on restricted graph classes?