Complexity of recognizing vertex-transitive graphs I am not knowledgeable in the area of complexity theory involving groups so I apologize if this is a well known result.


  Question 1. Let $G$ be a simple undirected graph of order $n$. What is the
  computational complexity (in terms of $n$) of determining if $G$ is
  vertex-transitive?


Recall that a graph $G$ is vertex-transitive if $\mathrm{Aut}(G)$ acts transitively on $V(G).$ 

I am not sure if the above definition allows for a polynomial time algorithm since it can be that the order of $\mathrm{Aut}(G)$ is exponential.

However vertex-transitive graphs have some other structural properties that might be exploited in order to be able to efficiently determine them so I am not sure what is the status of the above question.

Another interesting subclass of vertex-transitive graphs that has even more structure is the class of Cayley graphs. So it is natural to also pose the following related question


  Question 2. What is the computational complexity of determing if a graph $G$ is a
  Cayley graph?
I don't have a complete answer, but I think both problems are open.



The paper by Jajcay, Malni&#x10D;, Maru&scaron;i&#x10D; [3] is related to your first question.
They provide some tools to test vertex-transitivity. They say in the introduction that:


  For a given finite graph $\Gamma$,
  it is decidedly hard to determine whether $\Gamma$ is vertex-transitive,
  and the ultimate answer comes usually only after a substantial part of
  the full automorphism group of $\Gamma$ has been determined.


Note that vertex-transitivity test can be done by testing graph isomorphism $n−1$ times.
Make two copies $G$ and $G'$ of your graph,
with special anchors (like paths of length $n+1$) at $u \in V(G)$ and $v \in V(G')$.
There is an isomorphism between $G$ and $G'$ if and only if
the original graph has an automorphism mapping $u$ to $v$.
Thus you can test vertex-tansitivity by fixing a vertex $x$,
and checking that there are automorphisms mapping $x$ to all the other vertices.

Also note that if vertex-transitivity test can be done in polynomial time,
then so is isomorphism test for vertex-transitive graphs.
This is because two vertex-transitive graphs are isomorphic if and only if
their disjoint union is vertex-transitive.
I believe that complexity of graph isomorphism for vertex-transitive graphs is not known.



For the 2nd question, I found a partial result.
A circulant graph is a Cayley graph on a cyclic group.
Evdokimov and Ponomarenko [2] show that recognition of
circulant graphs can be done in polynomial time.
Also the book chapter by Alspach [1, Chapter 6: Cayley graphs, Section 6.2: Recognition]
would be interesting for you, although it says that:


  We shall ignore the computational problem of recognizing whether an
  arbitrary graph is a Cayley graph. Instead, we always assume that
  Cayley graphs have been described in terms of the groups on which they
  are built, together with the connection sets. For most problems this
  is not a drawback.





Beineke, Wilson, Cameron. Topics in Algebraic Graph Theory. Cambridge University Press, 2004. 
Evdokimov, Ponomarenko. Circulant graphs: Recognizing and isomorphism testing in polynomial time. St. Petersburg Math. J. 15 (2004) 813-835. doi:10.1090/S1061-0022-04-00833-7
Jajcay, Malni&#x10D;, Maru&scaron;i&#x10D;. On the number of closed walks in vertex-transitive graphs. Discrete Math. 307 (2007) 484-493. doi:10.1016/j.disc.2005.09.039