3
$\begingroup$

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.

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).

$\endgroup$
  • $\begingroup$ I don't understand the claims about graph automorphism. When $\epsilon=0$, the problem is trivial (the answer is always yes). $\endgroup$ – Emil Jeřábek Jul 14 '14 at 14:40
  • $\begingroup$ I guess the question should be "Is there a nontrivial automorphism" in the case $\epsilon=0$. $\endgroup$ – Janne Kokkala Jul 14 '14 at 14:43
  • $\begingroup$ 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. $\endgroup$ – Kimball Jul 16 '14 at 12:01
  • $\begingroup$ Ah, Emil Jeřábek pointed out I misread the question, as well as Erik Rijcken's comment. Answer deleted. $\endgroup$ – Kimball Jul 17 '14 at 11:47
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Very nice construction. $\endgroup$ – Emil Jeřábek Jul 30 '14 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.