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 ve rtices 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 prob lem is NP complete.) The authors prove sufficient conditions for the e xistence of edge-disjoint paths connecting any set of q less than or e qual to n/(log n)(kappa) disjoint pairs of vertices on any n vertex bo unded degree expander, where kappa depends only on the expansion prope rties of the input graph, and not on n. Furthermore, a randomized o(n( 3)) time algorithm, and a random NC algorithm for constructing these p aths is presented. (Previous existence proofs and construction algorit hms 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 suff iciently strong expander into two edge-disjoint spanning expanders.