Optimal Construction of Edge-Disjoint Paths in Random Graphs
Andrei Broder, ALAN M. FRIEZE, Stephen Suen, Eli Upfal · SIAM Journal on Computing · 1998
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 ${\cal NP}$-complete, although it is in ${\cal 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.