11

Given any simple undirected graph G, it is nontrivial to determine if G has nontrivial (non-identity) automorphisms. But what are results on upper/lower bounds of this decision problem?

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
Charles Yu
  • 131
  • 4

1 Answers1

15

Determining if a graph has a nontrivial automorphism Cook-reduces (polynomial time Turing) to Graph Isomorphism (determine if a pair of graphs is isomorphic) (exercise for the reader). It is not known to be equivalent to graph isomorphism.

In turn, graph isomorphism can be solved in $2^{\tilde O(\sqrt{n})}$ time and lies in $NP \cap coAM$. In particular, it is not $NP$-complete unless the polynomial hierarchy collapses.

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • So $GA\in P^{GI}$? I thought $GA$ many one reduces to $GI$. Am I wrong? Also is it known $GI\in BPP^{GA}$ or is even this beyond reach? – Turbo May 12 '17 at 13:53
  • 1
    Note that you don't need Turing reductions: There is even a polynomial-time many-one reduction from the nontrivial graph automorphism problem (GA) to graph isomorphism (GI). See Köbler, Schöning, Torán, "The Graph Isomorphism Problem: Its Structural Complexity", Corollary 1.43. This uses the fact that there is a polynomial-time computable or-function for GI. – a3nm Sep 07 '23 at 18:35