I'm interested in a variant of graph automorphism problem (which is prime candidate for $NP$-Intermediate problem).
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).