0
$\begingroup$

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}$?

Improve this question
$\endgroup$
2
  • $\begingroup$ 1. Must the vertex-pair $(2i,2i+1)$ in $G$ correspond to some vertex-pair $(2j,2j+1)$ in $H$? Or is it allowed to correspond to a vertex-pair $(2j+1,2j)$ in $H$ (i.e., $2i$ in $G$ corresponds to $2j+1$ in $H$, and $2i+1$ in $G$ corresponds to $2j$ in $H$)? 2. What have you tried? Where did you get stuck? Did you consider any reduction strategies, and if so, which ones, and where did you get stuck with them? $\endgroup$ – D.W.♦ Feb 29 '16 at 21:59
  • $\begingroup$ @D.W. $(2i-1,2i)$ has to correspond to $(2j-1,2j)$. $\endgroup$ – user39969 Feb 29 '16 at 22:12
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Say if $(2i_1-1,2i_1)$ and $(2i_2-1,2i_2)$ gets permuted to $(2j_1-1,2j_1)$ and $(2j_2-1,2j_2)$ then so does $(2i_1-1,2i_2)$ and $(2i_2-1,2i_1)$ gets permuted to $(2j_1-1,2j_1)$ and $(2j_2-1,2j_2)$ respectively for a different permutation. I do not want this. $\endgroup$ – user39969 Feb 29 '16 at 22:30
  • $\begingroup$ @Arul, OK, that's fine, but I don't think that's what your question asks. It sounds like what you want and what you wrote in the question are two different things. To be honest, I don't really understand what you want. You might want to consider asking a new question, and in that question be more careful to clearly specify the problem statement in the new question (give precise definitions, etc.). $\endgroup$ – D.W.♦ Feb 29 '16 at 22:36
  • $\begingroup$ I thought the $n!$ made it clear though. $\endgroup$ – user39969 Feb 29 '16 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy