Given a digraph D = (V;A) and a set of k pairs of vertices in V , we are interested in finding for each pair (x_i, y_i), a directed path connecting x_i to y_i, such that the set of k paths so found is arc-disjoint. For arbitrary graphs the problem is NP-complete, even for k = 2.

We present a polynomial time randomized algorithm for finding arc-disjoint paths in an r-regular expander digraph D We show that if D has sufficiently strong expansion properties and r is sufficiently large then all sets of k = \Omega (n/\log n) pairs of vertices can be joined. This is within a constant factor of best possible.