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?
Problem of graph bi-partition (related to graph isomorphism)
graph theory;graph algorithms;graph isomorphism;np complete
Your problem is NP-complete. Two-colorable perfect matching (which is NP-complete even when restricted to cubic planar graphs) is reducible to your problem. Take $H_1$ and $H_2$ to be perfect matchings each of $|V|/2$ nodes. Then your problem is to find 2-coloring of $V$ such that each color class induces a perfect matching. 