Computing Graph Automorphism from Partial Solutions

It is known that, given two isomorphic graphs G and H, finding a pair of vertices (v _i ,w _j ) where v _i is mapped to w _j by an isomorphism from G to H is as hard as computing an isomorphism from G to H. In this paper, we prove a similar result for the Graph Automorphism problem. That is to say, we prove that, given a graph that has a non-trivial automorphism, finding a pair of vertices (v _i ,v _j ) where v _i is mapped to v _j by a non-trivial automorphism on the graph is as hard as computing a non-trivial automorphism on the graph.