# How hard is a variant of graph automorphism problem?

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.

• I don't understand the claims about graph automorphism. When $\epsilon=0$, the problem is trivial (the answer is always yes). Jul 14, 2014 at 14:40
• I guess the question should be "Is there a nontrivial automorphism" in the case $\epsilon=0$. Jul 14, 2014 at 14:43
• Isn't graph automorphism itself already GI-hard? Did you try the approach I suggested in my answer? I will edit to make the heuristic more clear. Jul 16, 2014 at 12:01
• Ah, Emil Jeřábek pointed out I misread the question, as well as Erik Rijcken's comment. Answer deleted. Jul 17, 2014 at 11:47

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.