# How hard is a variant of graph automorphism problem?

I'm interested in a variant of graph automorphism problem (which is $NPI$ candidate).

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 \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

• All node pairs $p_i=(u_i, v_i)$ are pair-wise disjoint. Jul 13 '14 at 4:05
• To make sure I understand correctly, is the following equivalent to your problem? Given an undirected graph $G(E,V)$ and a partition of $V$ (the vertices) into parts of size exactly two, is there an automorphism such that, for each part $\{u_i, v_i\}$ of the partition, either $f(u_i) = v_i$ or $f(v_i) = u_i$. Jul 13 '14 at 6:33
• @JoshuaGrochow since your comment, I edited the question. The pairs do not form a partition of $V$. Jul 13 '14 at 10:21
• This question is cross-posted to MathOverflow at mathoverflow.net/questions/176073 . Next time you cross-post, please link the posts both ways. Jul 14 '14 at 9:45
• In addition, you are not supposed to simultaneously cross-post: you should only consider cross-posting if a reasonable amount of time has passed (say a week) with no answers on one of the forums; and you should cross-link them and update both to summarize what has been found on the other. See the faq for details.
– D.W.
Jul 31 '14 at 6:45

As far as I can see, Restricted GA is NP-complete. My proof has been originally posted here

If I understood well the question, this is an attempt to prove that your problem is $GI$-complete.

Given two graphs $G_1, G_2$ connect all the nodes of $G_1$ to a new node $x$ and all the nodes of $G_2$ to a new node $y$. Then connect $x$ and $y$ with a path of new nodes: $x_1, x_2, ... x_k,\; z\;, y_k, ...,y_2, y_1$ (there is an odd number of nodes between $x$ and $y$, and $z$ is the central node). Now you can pick some pairs of nodes at the two endpoints: $(x,y),(x_1,y_1),(x_2,y_2),...$. In this way you end up with an instance of your problem that has a solution if and only if the two original graphs are isomorphic.

• Nice! The proof looks right to me. But this is just a GI-hardness proof; it isn't immediately clear to me that GI is an upper bound. I don't see why GI-hardness would make it hard to prove that the problem is NP-hard. Also, although it is obviously hard to prove unconditionally that it is not NP-complete, one could hope to prove that it is in, say, coAM, and hence only NP-complete if PH collapses. Again, I don't see why a GI-hardness result should make a coAM upper bound any more difficult... Jul 14 '14 at 13:49
• @JoshuaGrochow: indeed you are right, I quickly wrote it and missed the correct order of $\leq$ ("it should be hard to prove that it is in P" looks better but it is obvious, so I deleted the final note at the end of the answer). Jul 14 '14 at 14:00
• I think I didn't get something, maybe both $G_1$ and $G_2$ are admitting automorphism, then this cannot be GI-complete (with current beliefs). P.S: But your reduction is a nice motivation toward NP-completeness of GI by considering NPC of fixed point free automorphism. Jul 14 '14 at 14:24
• What software are you using for graph drawing?
– joro
Jul 14 '14 at 15:32
• @joro: yEd ... great tool for (visual) drawing graphs very quickly (but not as powerful as TikZiT, especially for rendering the labels) Jul 14 '14 at 15:44