I'm interested in a variant of graph automorphism problem (which is $NPI$ candidate).
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 \le \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. 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.
EDIT: Cross-posted on mathOverflow