Computational complexity of computing a partial solution for the Graph Automorphism problems

It is known that a nontrivial automorphism on a given graph is computed by using any oracle that computes a pair of vertices (u,v) such that u is mapped to v by some nontrivial automorphism. In this paper, we consider a weaker oracle acting as follows. For a given graph, the oracle returns a pair (v,b) of a vertex v and a bit b∈{0,1} with the promise that if it returns (v,0), then the vertex v is fixed by some nontrivial automorphism, but if it returns (v,1), then the vertex v is moved by some nontrivial automorphism, provided that the given graph has a nontrivial automorphism. We here note that the oracle may return an arbitrary pair as its answer in case that the given graph has no nontrivial automorphism. We then show a stronger result that such an oracle is still powerful enough to compute a nontrivial automorphism. We also show that a similar result holds for RightGA, a GA-complete problem. We further investigate the computational complexity of computing a partial solution for PrefixGA which is known to be GI-complete. For this problem, we show that, when we consider any oracle similar to one mentioned above, the oracle does not help us to solve PrefixGA unless GI GA.