MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

My answer to the same question posted in cstheory got accepted by the OP, it's here:

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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