Routing permutations on graphs via matchings (extended abstract)

We consider a class of routing problems on connected graphs G. Initially, each vertex v of G is occupied by a "pebble" which has a unique destination in G, so that tt is a permutation of the vertices of G. It is required to route all the pebbles to their respective destinations by performing a sequence of moves of the following type: A disjoint set of edges is selected and the pebbles at each edge's endpoints are interchanged. The problem of interest is to minimize the number of steps required for any possible permutation x. The odd-even sorting network shows that in the very special case that G is an n-vertex path, any permutation can be routed in n steps. Here we investigate this routing problem for a variety of graphs G, including trees, complete graphs, hypercubes, Cartesian products of graphs, expander graphs and various Cayley graphs. In addition, we relate this routing problem to certain network flow problems, and to several graph invariants including diameter, eigenvalues and expansion coefficients. Three of our results are the following: (i) Any permutation can be routed on any n-vertex connected graph in less than 3n steps. For any regular graph on n vertices in which the absolute value of any nontrivial eigenvlaue is at most A, any permutation can be routed in 0{d2 log2 n/(d -A)2) steps. For any Cayley graph of a group of n elements with respect to a polylogarithmic (in n) number of generators, any permutation can be routed in a polylogarithmic number of steps if and only if the diameter of the graph is polylogarithmic.