Optimal Construction of Edge-Disjoint Paths in Random Graphs

Given a graph G = (V; E) with n vertices, and m edges, and a family of 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 paths so found is edge-disjoint. (For arbitrary graphs the problem is NP- complete, although it is in P if 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 Gn;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 non-trivial class of graphs. 1 Introduction Given a graph G = (V; E) with n vertices, and m edges, and a set of 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 paths so found is edge-disjoint. Digital Syst..