Complexity of algorithm to test if a graph is asymmetric

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.

• Please check complexity class 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.) Sep 12 '12 at 16:13

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.