# NP-hardness of a graph partition problem?

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 without any answer.

• Well, I don't have a formal proof now, but I think that it should be NP-hard. Take a look at problem GT12 of Garey and Johnson, which is quite similar. In that problem, the instance is a graph $G$, and a smaller graph $H$, and the question is whether you can partition the vertices of $G$ into isomorphic copies of $H$. Intuitively, the fact that the vertex set of both copies are not necessarily disjoint should make the problem harder. – Hebert Mar 3 '12 at 21:54
• Thanks Hebert. GT12 is different since the required isomorphism is fixed by graph $H$. – Mohammad Al-Turkistany Mar 4 '12 at 14:27
• isn't this problem harder than graph bi-partition? – Suvrit Mar 4 '12 at 18:51