16

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.

Community
  • 1
Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • 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). – Saeed Mar 01 '12 at 15:01
  • @Saeed, GI, which is not known to be in P, is reducible to this problem. – Mohammad Al-Turkistany Mar 01 '12 at 15:41
  • 1
    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 Mar 01 '12 at 18:20
  • 1
    I think you can assume $V_1=V_2=V$. – didest Mar 03 '12 at 18:27
  • @Diego, In general, you can not assume that $V_1=V_2=V$ – Mohammad Al-Turkistany Mar 03 '12 at 19:23
  • 1
    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 Mar 03 '12 at 23:05

1 Answers1

7

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.

didest
  • 1,551
  • 16
  • 25