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 is an element of {0, 1} with the promise that if it returns (u. 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 LIS to solve PreflxGA unless GI <=(P)(T) GA. (C) 2009 Elsevier B.V. All rights reserved.
computational complexity partial solution graph automorphism reducibility