I'm interested in a variant of graph automorphism problem (which is prime candidate for $NP$-Intermediate problem).

**Restricted GA**

Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ pairs of nodes $(u, v)$ where $u \ne v$ ( all pairs $(u_i, v_i)$ are pair-wise disjoint and $0 \lt \epsilon \le 1$)

Question: Is there a non-trivial automorphism $f$ of $G$ such that for every pair $p_i$ either $v_i=f(u_i)$ or $u_i= f(v_i)$?

This problem is at least as hard as Graph Automorphism Problem (when $\epsilon = 0$). I guess it is harder than Graph Automorphism but not $NP$-hard.

Is there a computational evidence that supports (or against) my guess regarding the complexity of this variant of $GA$?

**Motivation**: My problem is a relaxation of NP-complete problem known as fixed-point free graph automorphism problem.

Posted on TCS SE without answers.

**EDIT July 16**: I received on TCS StackExchange a partial answer which only shows that my problem is $GI$-hard. It would be great if someone finds conditional proof (assuming some complexity-theoretic conjecture) that my problem can not be $NP$-complete. This is the most interesting part (when we compare it to the fixed-point free automorphism problem). Such conditional proof would be an excellent evidence to support my guess.

**EDIT April 9th**: Can someone improve the answer by providing a drawing that illustrates the constructed graph in the reduction (assume $\epsilon =1$)? I am asking for this because I do not have the required tool and I find it hard to follow the graph construction (without a drawing).

nontrivialautomorphism" in the case $\epsilon=0$. $\endgroup$ – Janne Kokkala Jul 14 '14 at 14:43