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, we are interested in finding for each pair (ai, bi), a path connecting ai to bi, such that the set of q paths so found is edge-disjoint. (For general graphs the related decision problem is NPcomplete.) We prove sufficient conditions for the existence of edge-disjoint paths connecting any set of q ≤ n/(log n) κ disjoint pairs of vertices on any n vertex bounded degree expander, where κ depends only on the expansion properties of the input graph, and not on n. Furthermore, we present a randomized o(n 3) time algorithm, and a random N C algorithm for constructing these paths. (Previous existence proofs and construction algorithms allowed only up to n ǫ pairs, for some ǫ ≪ 1/3, and strong expanders [19].) In passing, we develop an algorithm for splitting a sufficiently strong expander into two edge-disjoint spanning expanders