NP-complete, and therefore may be NP-intermediate.

The easier problem of testing whether a graph has any symmetries (nontrivial automorphisms), known as the graph automorphism problem, also has no known polynomial time solution. There is a polynomial time algorithm for solving the graph automorphism problem for graphs where vertex degrees are bounded by a constant.The graph