Edge-Disjoint Paths in Expanders: Online with Removals

Abstract. We consider the problem of finding edge-disjoint paths between given pairs of vertices in a sufficiently strong [Formula: see text]-regular expander graph [Formula: see text] with [Formula: see text] vertices. In particular, we describe a deterministic, polynomial time algorithm which maintains an initially empty collection of edge-disjoint paths [Formula: see text] in [Formula: see text] and fulfills any series of two types of requests: (1) Given two vertices [Formula: see text] and [Formula: see text] such that each appears as an endpoint in [Formula: see text] paths in [Formula: see text] and, additionally, [Formula: see text], the algorithm finds a path of length at most [Formula: see text] connecting [Formula: see text] and [Formula: see text] which is edge-disjoint from all other paths in [Formula: see text], and adds it to [Formula: see text]. (2) Remove a given path [Formula: see text] from [Formula: see text]. 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. We obtain the same result in the case [Formula: see text] is directed.