NP-hardness of a graph partition problem? - MathOverflow 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 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 Answer by Diego de Estrada for NP-hardness of a graph partition problem? 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>