Optimal construction of edge-disjoint paths in random graphs

Given a graph G = (V, E) with n vertices, m edges, and a family of kappa pairs of vertices in V, we are interested in finding for each pair (a(i); b(i)) a path connecting a(i) to b(i) such that the set of kappa paths so found is edge disjoint. (For arbitrary graphs the problem is NP-complete, although it is in P if kappa is fixed.) We present a polynomial time randomized algorithm for finding the optimal number of edge disjoint paths (up to constant factors) in the random graph G(n,m) for all edge densities above the connectivity threshold. (The graph is chosen first; then an adversary chooses the pairs of endpoints.) Our results give the first tight bounds for the edge-disjoint paths problem for any nontrivial class of graphs.