Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

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.