most recent 30 from http://mathoverflow.net 2013-06-19T05:41:23Z http://mathoverflow.net/feeds/question/90123 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90123/np-hardness-of-a-graph-partition-problem Mohammad Al-Turkistany 2012-03-03T16:00:05Z 2012-03-05T18:29:56Z

<p>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$.</p> <p>This problem is at least as hard as Graph Isomorphism Problem. I guess it is harder than Graph Isomorphism but not NP-hard.</p> <blockquote> <p>Is this partition problem $NP$-hard?</p> </blockquote> <p>I posted it on <a href="http://cstheory.stackexchange.com/questions/10477/np-hardness-of-a-graph-partition-problem" rel="nofollow">CS theory</a> without any answer.</p>

http://mathoverflow.net/questions/90123/np-hardness-of-a-graph-partition-problem/90298#90298 Diego de Estrada 2012-03-05T18:29:56Z 2012-03-05T18:29:56Z

<p>My answer to the same question posted in cstheory got accepted by the OP, it's here: <a href="http://cstheory.stackexchange.com/a/10528/168" rel="nofollow">http://cstheory.stackexchange.com/a/10528/168</a></p>