Given a graph G = (V, E) and a set of κ
pairs of vertices in V, we are interested in finding,
for each pair (ai, bi),
a path connecting ai to bi
such that the set of κ paths so found is
edge-disjoint. (For arbitrary graphs the problem is [Nscr ][Pscr ]-complete, although it is in
[Pscr ] if κ is fixed.)
We present a polynomial time randomized algorithm for finding edge-disjoint paths in
the random regular graph Gn,r,
for sufficiently large r. (The graph is chosen first, then an
adversary chooses the pairs of end-points.) We show that almost every
Gn,r is such that all
sets of κ = Ω(n/log n) pairs of vertices can be joined.
This is within a constant factor of the optimum.