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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Hebert Mar 3 '12 at 21:54
  • $\begingroup$ Thanks Hebert. GT12 is different since the required isomorphism is fixed by graph $H$. $\endgroup$ – Mohammad Al-Turkistany Mar 4 '12 at 14:27
  • $\begingroup$ isn't this problem harder than graph bi-partition? $\endgroup$ – Suvrit Mar 4 '12 at 18:51

My answer to the same question posted in cstheory got accepted by the OP, it's here: https://cstheory.stackexchange.com/a/10528/168

| cite | improve this answer | |

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.