The standard way to find the shortest path between 2 vertices, $v_1$ and $v_2$, of an undirected graph is BFS (breadth first search) which takes time $O(|E|)$ and space $O(|V|)$ (where $E$ is the set of edges and $V$ is the set of vertices).
This paper: Frontier Search describes a way to solve the same problem with $O(|E|log|P|)$ time and $O(S)$ space, where $|P|$ is the length of the shortest path between $v_1$ and $v_2$ and $S$ is the cardinality of the largest sphere centered at $v_1$ (a sphere on the graph as a metric space, the length of each edge is $1$).
This is a major space reduction when the graph is essentially a layers graph with the largest layer being much smaller than the number of vertices in the graph.
I am wondering if this can be useful in searching for shortest paths in Cayley graphs.
For example, taking the group $\mathbb{Z_n} \times \mathbb{Z}_n$ with generators $(1,0)$ and $(0,1)$ we get that the cardinality of the largest sphere is $O(n)$ while the number of vertices in the graph is $O(n^2)$. Ofcourse, this is a silly example, because finding shortest paths in this Cayley graph is straightforward.
Another example is the Heisenberg group modulo an odd prime $p$, which, with the standard generators described in Wikipedia gives a Cayley graph of size $O(p^3)$ and a largest layer of size $O(p^2)$ (If I am not mistaken). This example is just a little less silly than the previous one, but only a little, because again - shortest paths on this graph can be found rather easily without performing any search.
I am looking for examples where this search method can be useful. To formulate what I am looking for, denote the largest sphere in the Cayley graph of the group $G$ by $LS(G)$ (I am droping the chosen set of generators just to simplify the notation).
Then I am looking for a sequence of finite groups $(G_{i})_{i=1}^{\infty}$ such that $|G_i|$ increases but $LS(G_i)/|G_i| \overset{i \rightarrow \infty}{\rightarrow} 0$ and there is no known efficient way to find shortest paths in the Cayley graphs of the groups $G_i$ (with some set of generators).
This idea also applies to infinite groups (with a set of generators) where spheres are much smaller than balls of the same radius, so such examples can be useful too (as long as finding shortest paths in their Cayley graphs is hard to do efficiently). A non-example would be the free group with 2 generators. A silly example would be the free abelian group with 2 generators. I know very little about growth rates of groups, but maybe any group with polynomial growth is an example?
