I am interested in shortest paths in the Cayley graph of the alternating group $A_{12}$ acting on the vertices of the icosahedron, where the generators are given by 5-cycles on the neighbors of any particular vertex.
Is there a decent algorithm for computing shortest paths in such a highly symmetric graph, given an explicit list of the generators? Brute force is doable, since there are only $12!/2$ different elements, but it would be nice to have a faster algorithm if one is available.
Background: If you place 12 unit spheres around a central unit sphere in 3D in an icosahedral configuration, each such generator can be realized without intersections or loss of contact by moving the 5 neighbors of an outer sphere P towards P inwards and spinning them around. http://en.wikipedia.org/wiki/Kissing_number#cite_note-1
Let $G$ be a finite group and $A \subset G$ a set of generators closed under inversion. Given $g \in G$, we seek a minimum length sequence $$g = a_1 \cdots a_k.$$ A sequence of length $k$ exists iff $\exists a_1 \cdots a_k = g$ iff $\exists a_1 \cdots a_{\lfloor k/2 \rfloor} = g a_1 \cdots a_{\lceil k/2 \rceil}$ iff $\exists a_L \in A^{\lfloor k/2 \rfloor}, a_R \in A^{\lceil k/2 \rceil}$ s.t. $a_L = g a_R$ iff $A^{\lfloor k/2 \rfloor} \cap g A^{\lceil k/2 \rceil} \ne \emptyset$.
If $|A^k|$ is exponential in $k$ up to near the diameter of $G$, this is a substantial savings over full brute force (something like $O(\sqrt{|G|})$ depending on the structure of $G$).