Was sind bekannte Grenzen der Komplexität des nichttrivialen Graphautomorphismus?

Bei jedem einfachen ungerichteten Graphen G ist es nicht trivial zu bestimmen, ob G nichttriviale (Nichtidentitäts-) Automorphismen aufweist. Aber was sind die Ergebnisse an den oberen / unteren Grenzen dieses Entscheidungsproblems?

Bestimmen, ob ein Graph einen nichttrivialen Automorphismus aufweist Cook-reduziert (Polynomzeit-Turing) auf Graph-Isomorphismus (bestimmen, ob ein Graphpaar isomorph ist) (Übung für den Leser). Es ist nicht bekannt, dass es dem Graphisomorphismus entspricht.

Der Graphisomorphismus kann wiederum in $2^{\tilde O(\sqrt{n})}$ Zeit gelöst werden und liegt in $NP \cap coAM$ . Insbesondere ist es nicht $NP$ vollständig , es sei denn, die Polynomhierarchie kollabiert.