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 (ai,bi), a path connecting a,-to bi, 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 ≤ n/(logn)κ 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 randomized o(n3) time algorithm, and a random NC algorithm for constructing these paths. (Previous existence proofs and construction algorithms allowed only up to ne pairs, for some ∈ ≪ 1/3, and strong expanders [16].) In passing, we develop an algorithm for splitting a sufficiently strong expander into two edge disjoint spanning expanders.