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.
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ 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.) $\endgroup$– Tsuyoshi ItoSep 12, 2012 at 16:13
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Dec 6, 2013 at 11:45
$\begingroup$
$\endgroup$
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.
