6
$\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?

I posted it on CS theory without any answer.

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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