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](https://cstheory.stackexchange.com/questions/25224/how-hard-is-a-variant-of-graph-automorphism-problem) without answers.


**EDIT July 16**: I received on TCS StackExchange a [partial answer](https://cstheory.stackexchange.com/a/25232/495) 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.



How hard is a variant of graph automorphism problem?
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](http://en.wikipedia.org/wiki/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.


