Abstract:
|
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. |