Connected Bipartite Vertex-transitive Graph Recognition

Question

For vertex-transitive graphs, the computational complexity of recognizing them is still unknown. So here comes the question: if it is guaranteed that the input graph is bipartite and connected, is the computational complexity of determining whether it is vertex-transitive or not known now?

Answer 1

Not a full answer, but just pointing out some relationships between the problems.

(1) The problem for bipartite graphs is as hard as the general problem for arbitrary graphs, this much we can prove.
(2) Similarly, the problem for connected bipartite graphs is no easier than the general problem for connected graphs.

To see this, we need a result from Vertex-Transitive Direct Products of Graphs by Hammack and Imrich (available for free via the Electronic Journal of Combinatorics).

The result is as follows:
Theorem 13: If $A$ and $B$ are both non-bipartite or both bipartite, then $A \times B$ is vertex transitive if and only if both $A$ and $B$ are vertex-transitive. If $A$ has an odd cycle and $B$ is bipartite, then $A \times B$ is vertex-transitive if and only if both $A \times K_2$ and $B$ are vertex transitive.

Using the second part of the theorem, we can see that for any non-bipartite graph $A$, the (bipartite!) graph $A\times K_2$ is vertex transitive if and only if $A$ is. So for a non-bipartite graph $A$, you can reduce the problem of determining whether it's vertex-transitive to the same problem on the bipartite graph $K_2\times A$. This proves statement (1).

Further note that for a non-bipartite $A$, $K_2\times A$ is connected if and only if $A$ is, demonstrating (2).