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.

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

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .