Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ induced by $S \subseteq V(G)$).
Has anyone ever encountered this problem ? I'm interested in any kind of characterization of graphs for which it is possible (or not), and on the hardness of problem. It's probably NP-Hard but why ?