<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-05-12T13:53:01.843Z
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
CC BY-SA 4.0
2023-09-07T18:35:52.607Z
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.
Antoine Amarilli 'a3nm'
CC BY-SA 2.5
2010-08-25T01:39:38.023Z
2010-08-25T01:39:38.023Z
Joshua Grochow
<p>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?</p>

<cc.complexity-theory><graph-isomorphism><automorphism>
what are known bounds on complexity of nontrivial graph automorphism
Charles Yu
# what are known bounds on complexity of nontrivial graph automorphism

(Asked by: username_0 on 2010-08-25)

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?

**Tags:** cc.complexity-theory, graph-isomorphism, automorphism

---

## 1 answers

### Answer by username_1 on 2010-08-25. Score: 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.

> **Comments:**
> **username_2**: 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?  
> **username_3**: 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.  

---

