Restricting possible permutations in Graph Isomorphism problem

Question

Given a $2n$ vertex undirected graph whose vertices are partitioned arbitrarily in pairs to say WLOG $(1,2)$, $(3,4)$, $\dots$, $(2n-1,2n)$. Call these vertices pairs as super vertices.

Call two such graphs $2n$ vertex labelled graphs $G$, $H$ whose adjacencies are $A$ and $B$ respectively $\mathsf{vertex}$-$\mathsf{pair}$-$\mathsf{isomorphic}$ iff there is a permutation $P$ such that $A=PBP'$ on the condition that the permutation $P$ permutes only supervertices (only a subset $n!$ of permutations of $(2n)!$ allowed). In particular, the permutation must map even-numbered vertices in $G$ to even-number vertices in $H$; and if vertex $2i$ in $G$ is mapped to vertex $2j$ in $H$ by the permutation, then vertex $2i-1$ in $G$ must be mapped to $2j-1$ in $H$.

Is $\mathsf{vertex}$-$\mathsf{pair}$-$\mathsf{isomorphic}$ $\mathsf{GI}$-$\mathsf{complete}$?

Answer 1

It's GI-complete. Here's a simple reduction. Let $G_0,H_0$ be any two connected, undirected graphs on $n$ vertices. Consider the vertices of $G_0$ as even-numbered vertices of $G$, and add $n$ odd-numbered vertices that aren't connected to anything. Construct $H$ from $H_0$ similarly. Now $G$ is vertex-pair-isomorphic to $H$ if and only if $G_0$ is isomorphic to $H$, so solving vertex-pair-isomorphism is at least as hard as solving graph isomorphism.