<p>The complement of your problem is known as graph automorphism problem (GA). It is a candidate for $NP$-intermediate problems. The problem is not known to be solvable in polynomial time. Also, It is not known to be $NP$-complete. It polynomialy reduces to the graph isomorphism problem (GI) but no known polynomial reduction from GI to GA. Unique-GI is equivalent to GA. </p>

CC BY-SA 3.0
2013-12-06T11:45:11.803Z
2013-12-06T12:05:30.410Z
2013-12-06T12:05:30.410Z
Mohammad Al-Turkistany
<p>I computed the black box number of permutations you have to test to prove the only automorphism is the identity permutation. <a href="http://oeis.org/A186202" rel="nofollow">http://oeis.org/A186202</a></p>

<p>If you can inspect the structure of the graph you can solve it much faster in practice.</p>

CC BY-SA 3.0
2013-12-10T16:55:40.507Z
2013-12-10T16:55:40.507Z
Chad Brewbaker
<p>Counting the order of automorphism group of a graph is polynomial-time equivalent to graph isomorphism problem. But if we just want to know if the order is greater than 1, what is the complexity of this problem? Graphs which have no automorphism except for the trivial one, that is identity permutation, are called asymmetric graphs. So the problem is to check if the graph is asymmetric.</p>

CC BY-SA 3.0
2012-09-12T16:13:08.710Z
Please check complexity class [GA](http://qwiki.stanford.edu/index.php/Complexity_Zoo:G#ga) and the book cited there.  (The definition of the graph automorphism problem in the Complexity Zoo is technically incorrect; this problem is usually defined as the decision problem to decide whether a given graph has any nontrivial automorphism.)
Tsuyoshi Ito
<cc.complexity-theory><graph-theory><graph-isomorphism><algebraic-complexity>
Complexity of algorithm to test if a graph is asymmetric
DurgaDatta
# Complexity of algorithm to test if a graph is asymmetric

(Asked by: username_0 on 2012-09-12)

Counting the order of automorphism group of a graph is polynomial-time equivalent to graph isomorphism problem. But if we just want to know if the order is greater than 1, what is the complexity of this problem? Graphs which have no automorphism except for the trivial one, that is identity permutation, are called asymmetric graphs. So the problem is to check if the graph is asymmetric.

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

> **Comments:**
> **username_1**: Please check complexity class [GA](http://qwiki.stanford.edu/index.php/Complexity_Zoo:G#ga) and the book cited there.  (The definition of the graph automorphism problem in the Complexity Zoo is technically incorrect; this problem is usually defined as the decision problem to decide whether a given graph has any nontrivial automorphism.)  

---

## 2 answers

### Answer by username_2 on 2013-12-06. Score: 1

The complement of your problem is known as graph automorphism problem (GA). It is a candidate for $NP$-intermediate problems. The problem is not known to be solvable in polynomial time. Also, It is not known to be $NP$-complete. It polynomialy reduces to the graph isomorphism problem (GI) but no known polynomial reduction from GI to GA. Unique-GI is equivalent to GA.


---

### Answer by username_3 on 2013-12-10. Score: 1

I computed the black box number of permutations you have to test to prove the only automorphism is the identity permutation. <http://oeis.org/A186202>

If you can inspect the structure of the graph you can solve it much faster in practice.


---

