Algorithm to test a graph for $t$-transitivity

I am looking for an algorithm, which given a graph $G$ and a natural number $t$, determines if $G$ is $t$-transitive.

I am also interested in knowing if this problem is in P, NP, NPC or some other interesting facts about its complexity class.

If you had an oracle from Graph Isomorphism, then for constant $t$ you can check whether a graph is $t$-transitive. For example, to check if a graph is $1$-transitive, for every vertex $i$ create a variant $G_i$ of your original graph by attaching an "appendage" at vertex $i$, say a very long path or a very large star. The graph is transitive if all $G_i,G_j$ are isomorphic.

StackExchange Computer Science Q#2527, answer score: 4