On the complexity of moving vertices in a graph
Antoni Lozano Bojados, Vijay Raghavan · 1998
We consider the problem of deciding whether a given graph G has an automorphism which moves at least k vertices (where k is a function of |V(G)|), a question originally posed by Lubiw (1981). Here we show that this problem is equivalent to the one of deciding whether a graph has a nontrivial automorphism, when k is O((log n)/(log log n)). It is commonly believed that deciding isomorphism between two graphs is strictly harder than deciding whether a graph has a nontrivial automorphism. Indeed, we show that an isomorphism oracle would improve the above result slightly---using such an oracle, one can decide whether there is an automorphism which moves at least k' vertices, where k is O(log n). If P is different from NP and Graph Isomorphism is not NP-complete, the above results are fairly tight, since it is known that deciding if there is an automorphism which moves at least n^e vertices, for any fixed e in (0, 1), is NP-complete. In other words, a substantial improvement of our result would settle some fundamental open problems about Graph Isomorphism.