An efficient algorithm for the vertex-disjoint paths problem in random graphs

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 vertex-disjoint. (The problem is NP-complete for general graphs as well as for planar graphs. It is in P if the number of pairs is fixed.) Our model is that the graph is chosen first, then an adversary chooses the pairs of endpoints, subject only to obvious feasibility constraints, namely, all pairs must be disjoint, no more than a constant fraction of the vertices could be required for the paths, and not "too many" neighbors of a vertex can be endpoints. We present a randomized polynomial time algorithm that works for almost all graphs; more precisely in the Gn,m or Gn, p models, the algorithm succeeds with high probability for all edge densities above the connectivity threshold. The set of pairs that can be accommodated is optimal up to constant factors. Although the analysis is intricate, the algorithm itself is quite simple and suggests a practical heuristic. We include two applications of the main result, one in the context of circuit switching communication, the other in the context of topological embeddings of graphs.