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?
> 
> 
> 


I posted it on [CS theory](https://cstheory.stackexchange.com/questions/10477/np-hardness-of-a-graph-partition-problem) without any answer.



NP-hardness of a graph partition problem?
My answer to the same question posted in cstheory got accepted by the OP, it's here: <https://cstheory.stackexchange.com/a/10528/168>


