# Problem of graph bi-partition (related to graph isomorphism)

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?

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.