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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Aug 25, 2010 at 1:39
-
$\begingroup$ 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? $\endgroup$– TurboMay 12, 2017 at 13:53
-
1$\begingroup$ 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. $\endgroup$– a3nmSep 7 at 18:35