EXISTENCE AND CONSTRUCTION OF EDGE-DISJOINT PATHS ON EXPANDER GRAPHS

Given an expander graph G = (V, E) and a set of q disjoint pairs of vertices in V, the authors are interested in finding for each pair (a(i), b(i)) a path connecting a(i) to b(i) such that the set of q paths so found is edge disjoint. (For general graphs the related decision problem is NP complete.) The authors prove sufficient conditions for the existence of edge-disjoint paths connecting any set of q less than or equal to n/(log n)(kappa) disjoint pairs of vertices on any n vertex bounded degree expander, where kappa depends only on the expansion properties of the input graph, and not on n. Furthermore, a randomized o(n(3)) time algorithm, and a random NC algorithm for constructing these paths is presented. (Previous existence proofs and construction algorithms allowed only up to n(epsilon) pairs, for some epsilon << (1/3, and strong expanders [D. Peleg and E. Upfal, Combinatorica, 9 (1989), pp.289-313.].) In passing, an algorithm is developed for splitting a sufficiently strong expander into two edge-disjoint spanning expanders.