Edge-disjoint paths in expanders: online with removals

We consider the problem of finding edge-disjoint paths between given pairs of vertices in a sufficiently strong d-regular expander graph G with n vertices. In particular, we describe a deterministic, polynomial time algorithm which maintains an initially empty collection of edge-disjoint paths P in G and fulfills any series of two types of requests:

1. Given two vertices a and b such that each appears as an endpoint in O(d) paths in P and, additionally, |P| = O(nd/ log n), the algorithm finds a path of length at most log n connecting a and b which is edge-disjoint from all other paths in P, and adds it to P.

2. Remove a given path P ∈ P from P.

Importantly, each request is processed before seeing the next one. The upper bound on the length of found paths and the constraints are the best possible up to a constant factor. This establishes the first online algorithm for finding edge-disjoint paths in expanders which also allows removals, significantly strengthening a long list of previous results on the topic.