Arc-Disjoint Paths in Expander Digraphs

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 ${\cal 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 {\em all} sets of $k=\Omega(n/\log n)$
pairs of vertices can be joined. This is within a constant factor
of best possible.

This is joint work with Tom Bohman