<p>I've found that this problem is NP-hard, even restricted to trees.
The reference is Graham and Robinson, "Isomorphic factorizations IX: even trees", but I couldn't get it.</p>

CC BY-SA 3.0
2012-03-05T13:35:12.500Z
2012-03-05T13:47:06.803Z
2012-03-05T13:47:06.803Z
didest
<p>I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic? </p>

<p>Here $E$ is partitioned into two disjoint sets $E_1$ and $E_2$. Sets $V_1$ and $V_2$ are not necessarily disjoint. $E1∪E2=E$ and $V1∪V2=V$.</p>

<p>This problem is at least as hard as Graph Isomorphism Problem. I guess it is harder than Graph Isomorphism but not NP-hard.</p>

<blockquote>
  <p>Is this partition problem $NP$-hard?</p>
</blockquote>

<p>EDIT 3-3-2012: Posted on <a href="https://mathoverflow.net/questions/90123/np-hardness-of-a-graph-partition-problem">MathOverflow</a>.</p>

<p>EDIT 3-5-2012: It turns out that the reference in Diego's answer is one of the unpublished results. After some digging, I found a reference to it in The NP-Completeness Column: An Ongoing Guide by David JOHNSON (page 8). I found other papers  that cite the NP-completeness result of Graham and Robinson as unpublished.   </p>

CC BY-SA 3.0
2012-03-01T15:01:39.273Z
I think you mean $E_1\cup E_2 = E$ and $V_1\cup V_2 = V$, else it's simply solvable in $P$ and I mentioned this because If $V_1$ and $V_2$ are disjoint, union can't be true in general case (for edges).
Saeed
CC BY-SA 3.0
2012-03-01T15:41:00.430Z
@Saeed, GI, which is not known to be in P, is reducible to this problem.
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-03-01T18:20:08.157Z
Seems related to the *symmetry breaking-preserving game* (see Harary's papers: "A Symmetric Strategy in Graph Avoidance Games", "On the Lengths of Symmetry Breaking-Preserving Games on Graphs") ... both "too far" from my level of expertise :-(
Marzio De Biasi
CC BY-SA 3.0
2012-03-03T18:27:38.610Z
I think you can assume $V_1=V_2=V$.
didest
CC BY-SA 3.0
2012-03-03T19:23:52.297Z
@Diego, In general, you can not assume that $V_1=V_2=V$
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-03-03T23:05:21.257Z
If $v\in V_1-V_2$, there exists a $w\in V_2-V_1$ since $|V_1|=|V_2|$. You can add $v$ to $V_2$ and $w$ to $V_1$ and map them in the isomorphism, since they are isolated in the subgraphs.
didest
<cc.complexity-theory><graph-theory><graph-isomorphism>
NP-hardness of a graph partition problem?
Mohammad Al-Turkistany
# NP-hardness of a graph partition problem?

(Asked by: username_0 on 2012-03-01)

I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G\_1(E\_1, V\_1)$ and $G\_2(E\_2, V\_2)$ such that $G\_1$ and $G\_2$ are isomorphic?

Here $E$ is partitioned into two disjoint sets $E\_1$ and $E\_2$. Sets $V\_1$ and $V\_2$ are not necessarily disjoint. $E1∪E2=E$ and $V1∪V2=V$.

This problem is at least as hard as Graph Isomorphism Problem. I guess it is harder than Graph Isomorphism but not NP-hard.

> Is this partition problem $NP$-hard?

EDIT 3-3-2012: Posted on [MathOverflow](https://mathoverflow.net/questions/90123/np-hardness-of-a-graph-partition-problem).

EDIT 3-5-2012: It turns out that the reference in Diego's answer is one of the unpublished results. After some digging, I found a reference to it in The NP-Completeness Column: An Ongoing Guide by David JOHNSON (page 8). I found other papers that cite the NP-completeness result of Graham and Robinson as unpublished.

**Tags:** cc.complexity-theory, graph-theory, graph-isomorphism
> **Comments:**
> **username_1**: I think you mean $E_1\cup E_2 = E$ and $V_1\cup V_2 = V$, else it's simply solvable in $P$ and I mentioned this because If $V_1$ and $V_2$ are disjoint, union can't be true in general case (for edges).  
> **username_0**: @Saeed, GI, which is not known to be in P, is reducible to this problem.  
> **username_2**: Seems related to the *symmetry breaking-preserving game* (see Harary's papers: "A Symmetric Strategy in Graph Avoidance Games", "On the Lengths of Symmetry Breaking-Preserving Games on Graphs") ... both "too far" from my level of expertise :-(  
> **username_3**: I think you can assume $V_1=V_2=V$.  
> **username_0**: @Diego, In general, you can not assume that $V_1=V_2=V$  
> **username_3**: If $v\in V_1-V_2$, there exists a $w\in V_2-V_1$ since $|V_1|=|V_2|$. You can add $v$ to $V_2$ and $w$ to $V_1$ and map them in the isomorphism, since they are isolated in the subgraphs.  

---

## 1 answers

### Answer by username_3 on 2012-03-05. Score: 7 | Accepted answer

I've found that this problem is NP-hard, even restricted to trees.
The reference is Graham and Robinson, "Isomorphic factorizations IX: even trees", but I couldn't get it.


---

