Finding disjoint paths in expanders deterministically and online

We describe a deterministic, polynomial time algorithm for finding edge-disjoint paths connecting given pairs of vertices in an expander. Specifically, the input of the algorithm is a sufficiently strong d-regular expander G on n vertices, and a sequence of pairs s_i, tⁱ, (1 ≤ i ≤ r) of vertices, where r = Θ(nd log d/log n), and no vertex appears more than d/3 times in the list of all endpoints s₁, t ₁,...,s_r,t_r. The algorithm outputs edge-disjoint paths Q₁,...,Q_r, where Q_i connects s_i and t_i. The paths are constructed online, that is, the algorithm produces Q_i as soon as it gets s_i, t_i and before the next requests in the sequence are revealed. This improves in several respects a long list of previous algorithms for the above problem, whose study is motivated by the investigation of communication networks. An analogous result is established for vertex disjoint paths in blow-ups of strong expanders.