11
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ I'm not sure if I understand the basic definition. Let me guess: the "layer sphere" of radius $r$ about the vertex $x$ is the set of vertices with distance exactly $r$ from $x$. Is that right? If so, you are asking for a sequence of graphs where the Cheeger constant goes to zero. That is, the graph has a "bottleneck". Since Cayley graphs are very symmetric, once you have one bottleneck, you have lots... so the group feels like it should be constrained in an interesting way. Here is the second link Google gives: en.wikipedia.org/wiki/Cheeger_constant_%28graph_theory%29 $\endgroup$
    – Sam Nead
    Mar 11, 2012 at 19:23
  • 1
    $\begingroup$ In the context of infinite finitely-generated groups, you are asking for amenable groups with unsolvable word problem (as far as I can tell). Olga Kharlampovich has a great example of a solvable group with unsolvable word problem: O. Kharlampovich, "A finitely presented solvable group with unsolvable word problem", Izvest. Ak. Nauk, Ser. Mat. 45, 4 (1981), 852–873. $\endgroup$
    – Misha
    Mar 11, 2012 at 19:35
  • 1
    $\begingroup$ @Misha: no, amenability does not imply that spheres are much smaller than balls because Foelner sets do not usually look like balls. "Spheres smaller than balls" is more related to subexponential growth which is much more restrictive than amenability. Kharlampovich's example has exponential growth. All groups of subexponenial growth that I know have easy word problem. $\endgroup$
    – user6976
    Mar 12, 2012 at 0:24
  • $\begingroup$ Yes, of course, thanks for the correction, Mark! And all known groups of intermediate growth act faithfully on rooted trees, so they are of no use for this problem. $\endgroup$
    – Misha
    Mar 12, 2012 at 19:40
  • 1
    $\begingroup$ @Misha: There are also examples by Anna Erschler that do not act faithfully on rooted trees, but the word problem is easy there too. $\endgroup$
    – user6976
    Mar 13, 2012 at 4:37

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.