16
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Saeed Mar 1 '12 at 15:01
  • $\begingroup$ @Saeed, GI, which is not known to be in P, is reducible to this problem. $\endgroup$ – Mohammad Al-Turkistany Mar 1 '12 at 15:41
  • 1
    $\begingroup$ 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 :-( $\endgroup$ – Marzio De Biasi Mar 1 '12 at 18:20
  • 1
    $\begingroup$ I think you can assume $V_1=V_2=V$. $\endgroup$ – Diego de Estrada Mar 3 '12 at 18:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Diego de Estrada Mar 3 '12 at 23:05
7
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.