Existence and construction of edge disjoint paths on expander graphs

Abstract: "Given an expander graph G = (V,E) and a set of K disjoint pairs of vertices in V, we are interested in finding for each pair (a[subscript i], b[subscript i]), a path connecting a[subscript i] to b[subscript i], such that the set of K paths so found is edge disjoint. (For general graphs the related decision problem is NP-complete.) We prove sufficient conditions for the existence of K [< or =] n/(log n)[superscript K] edge disjoint paths connecting any set of K disjoint pairs of vertices on any n vertex bounded degree expander, where K depends only on the expansion properties of the input graph, and not on n. Furthermore, we present a randomizedo(n┬│) [sic] time algorithm, and a random NC algorithm forconstructing [sic] these paths. (Previous existence proofs and construction algorithms allowed only up to n[superscript epsilon] pairs, for some [epsilon] << 1/3, and strong expanders [17].) In passing, we develop an algorithm for splitting a sufficiently strong expander into two edge disjoint spanning expanders."