How hard is a variant of graph automorphism problem?

Question

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.

Answer 1

The problem is NP-hard, as far as I can see. Here is a reduction to it from a certain NP-complete satisfiability problem. Let $e(x_i,x_j,x_k,x_l)$ denote a Boolean formula which is true if and only if exactly two of literals $x_i,x_j,x_k,x_l$ are true. By Schaefer's dichotomy theorem, it is NP-hard to decide whether a given conjunction $\psi$ of the constraints $e(x_i,x_j,x_k,x_l)$ is satisfiable or not.

The reduction goes as follows. For any variable $x_i$, we construct a triangle on vertices $x_{i1},x_{i2},x_{i3}$, and we also draw a simple cycle of length $i$ on every of $x_{i1},x_{i2},x_{i3}$ to ensure that any automorphism sends $x_{ia}$ to $x_{ib}$. The specified pairs of nodes are $(x_{i1},x_{i2})$ over all $i$.

For any constraint $e_t=e(x_i,x_j,x_k,x_l)$ from $\psi$, add vertices $v_{tpqrs}$ which correspond to tuples $(p,q,r,s)\in\{1,2,3\}^4$ such that $p+q+r+s$ is divisible by three. Draw a simple cycle on $v_{tqprs}$ with $t$ vertices to ensure that $v_{tqprs}$ is sent to $v_{tq'p'r's'}$ by any automorphism. Finally, connect $v_{tqprs}$ by edges with $x_{ip}$, $x_{jq}$, $x_{kr}$, $x_{ls}$.

I claim $\psi$ is satisfiable if and only if the constructed graph has an automorphism $\varphi$ which satisfies, for every $i$, either $\varphi(x_{i1})=x_{i2}$ or $\varphi(x_{i2})=x_{i1}$. In fact, we define $x_i=1$ iff it is the latter case, that is, $\varphi$ sends $x_{i,p}$ to $x_{i,p+1}$, for any $p$; we define $x_i=0$ iff it is the former case, that is, $x_{i,p}$ is sent to $x_{i,p-1}$. For $\varphi$ such an automorphism, assume $x_{ip}$, $x_{jq}$, $x_{kr}$, $x_{ls}$ are incident to some $v_{tqprs}$; then, their images $x_{ip'}$, $x_{jq'}$, $x_{kr'}$, $x_{ls'}$ are also incident to $v_{tq'p'r's'}$. Therefore, $p'+q'+r'+s'$ divides three, so that precisely two of $x_{i}$, $x_{j}$, $x_{k}$, $x_{l}$ are true, making true the $\psi$ formula. Conversely, if $\psi(x_1,\ldots,x_n)$ is true, then we define $\varphi(x_{ip})$ as above and send $v_{tqprs}$ to $v_{tq'p'r's'}$ in the above notation, to construct a required automorphism.

Finally, note that the number of specified vertex pairs $(x_{i1},x_{i2})$ is less than required $\varepsilon|V|$ in the present graph. This is not crucial as we can add a sufficient number of isolated edges to a graph which will not break the automorphism properties discussed above.