I'm working on a problem related to Latin squares, and I want software for what essentially boils down to the decision problem:

Input: A finite, simple graph G.
Output: YES if G has a non-trivial automorphism, NO otherwise.

Hence...

Question: Is there an efficient algorithm or software for determining whether or not a graph has a non-trivial automorphism?

We could use Nauty or Bliss (and possibly some other packages) to compute the whole automorphism group, but I don't need it; all I need to determine is whether or not it's trivial.

It's possible this decision problem is theoretically equivalent in complexity to "compute the whole automorphism group" in some way. I'm not sure.

I'm working on a problem related to Latin squares, and I want a method for what essentially boils down to the decision problem:

Input: A finite, simple graph G.
Output: YES if G has a non-trivial automorphism, NO otherwise.

Hence...

Question: Is there an efficient algorithm for determining whether or not a graph has a non-trivial automorphism?

We could use Nauty or Bliss (and possibly some other packages) to compute the whole automorphism group, but I don't need it; all I need to determine is whether or not it's trivial.

It's possible this decision problem is theoretically equivalent in complexity to "compute the whole automorphism group" in some way. I'm not sure.

For my purpose, "efficient" basically means "faster in practice than computing the whole automorphism group", but I'm also interested in the theory behind it.