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

EDIT 3-3-2012: Posted on MathOverflow.

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.

• 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). Mar 1 '12 at 15:01
• @Saeed, GI, which is not known to be in P, is reducible to this problem. Mar 1 '12 at 15:41
• 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 :-( Mar 1 '12 at 18:20
• I think you can assume $V_1=V_2=V$. Mar 3 '12 at 18:27
• 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. Mar 3 '12 at 23:05