<p>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. </p>

CC BY-SA 3.0
2016-04-27T13:50:31.377Z
Splendid! If anyone's interested, it appears that this result is from Schaeffer '78 *The Complexity of Satisfiability Problems*
tarulen
CC BY-SA 3.0
2016-04-27T13:40:11.643Z
2016-04-27T13:40:11.643Z
Mohammad Al-Turkistany
<p>I am considering the following problem:</p>

<blockquote>
  <p><strong>Input:</strong> 3 graphs $G=(V,E)$, $H_1$, $H_2$<br>
  <strong>Question:</strong> 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$?</p>
</blockquote>

<p>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.</p>

<p>I have several questions regarding this:</p>

<ul>
<li>Has it been studied / does it have a name?</li>
<li>If yes, is it NP-hard?</li>
<li>If still yes, has it been studied on restricted graph classes?</li>
</ul>

<graph-theory><graph-algorithms><graph-isomorphism><np-complete>
Problem of graph bi-partition (related to graph isomorphism)
tarulen
# Problem of graph bi-partition (related to graph isomorphism)

(Asked by: username_0 on 2016-04-27)

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?

**Tags:** graph-theory, graph-algorithms, graph-isomorphism, np-complete

---

## 1 answers

### Answer by username_1 on 2016-04-27. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: Splendid! If anyone's interested, it appears that this result is from Schaeffer '78 *The Complexity of Satisfiability Problems*  

---

