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

EDIT 3-3-2012: Posted on MathOverflow.

EDIT 3-5-2012: It turns out that the reference in Diego's answer is one of the unpublished results. After some digging, I found a reference to it in The NP-Completeness Column: An Ongoing Guide by David JOHNSON (page 8). I found other papers that cite the NP-completeness result of Graham and Robinson as unpublished.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I think you mean $E_1\cup E_2 = E$ and $V_1\cup V_2 = V$, else it's simply solvable in $P$ and I mentioned this because If $V_1$ and $V_2$ are disjoint, union can't be true in general case (for edges). $\endgroup$
    – Saeed
    Mar 1, 2012 at 15:01
  • $\begingroup$ @Saeed, GI, which is not known to be in P, is reducible to this problem. $\endgroup$
    – Mohammad Al-Turkistany
    Mar 1, 2012 at 15:41
  • 1
    $\begingroup$ Seems related to the symmetry breaking-preserving game (see Harary's papers: "A Symmetric Strategy in Graph Avoidance Games", "On the Lengths of Symmetry Breaking-Preserving Games on Graphs") ... both "too far" from my level of expertise :-( $\endgroup$
    – Marzio De Biasi
    Mar 1, 2012 at 18:20
  • 1
    $\begingroup$ I think you can assume $V_1=V_2=V$. $\endgroup$
    – didest
    Mar 3, 2012 at 18:27
  • 1
    $\begingroup$ If $v\in V_1-V_2$, there exists a $w\in V_2-V_1$ since $|V_1|=|V_2|$. You can add $v$ to $V_2$ and $w$ to $V_1$ and map them in the isomorphism, since they are isolated in the subgraphs. $\endgroup$
    – didest
    Mar 3, 2012 at 23:05

1 Answer 1

Reset to default
7
+50
$\begingroup$

I've found that this problem is NP-hard, even restricted to trees. The reference is Graham and Robinson, "Isomorphic factorizations IX: even trees", but I couldn't get it.

Improve this answer
$\endgroup$
0

Your Answer

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

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