I'm interested to find out the complexity of the following problem:
Given a finite simplicial (unoriented, with no loops and multiple edges) graph $\Gamma = (V\Gamma, E\Gamma)$, decide whether or not there exists $v \in V\Gamma$ such that $\mathop{stab}(B(1,v)) \leq \mathop{Aut}(\Gamma)$, the stabliser of the ball of radius (with respect to the path metric) centred around $v$, is non-trivial.
We assume that the graph $\Gamma$ is presented on input as a list of vertices and edges.