Existence and Construction of Edge-Disjoint Paths on Expander Graphs
Andrei Broder, ALAN M. FRIEZE, Eli Upfal · SIAM Journal on Computing · 1994
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 \leqslant {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 $\mathcal{NC}$ algorithm for constructing these paths is presented. (Previous existence proofs and construction algorithms allowed only up to $n^ \epsilon $ pairs, for some $ \epsilon \ll \frac{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.