Efficient oracles and routing schemes for replacement paths

Real life graphs and networks are prone to failure of nodes (vertices) and links (edges). In particular, for a pair of nodes s and t and a failing edge e in an n-vertex unweighted graph G = (V (G), E(G)), the replacement path pG-e(s, t) is a shortest s- t path that avoids e. In this paper we present several efficient constructions that, for every (s, t) ? S ×T, where S, T ? V (G), and every e ? E(G), maintain the collection of all pG-e(s, t), either implicitly (i.e., through compact data structures a.k.a. distance sensitivity oracles (DSO)), or explicitly (i.e., through sparse subgraphs a.k.a. fault-tolerant preservers (FTP)). More precisely, we provide the following results: (1) DSO: For every S, T ? V (G), we construct a DSO for maintaining S × T distances under single edge (or vertex) faults. This DSO has size O(n|S||T|) and query time of O(|S||T|). At the expense of having quasi-polynomial query time, the size of the oracle can be improved to O(n|S| + |T||S|n), which is optimal for |T| = (n|S|). When |T| = (n4 3|S|1 4), the construction can be further refined in order to get a polynomial query time. We also consider the approximate additive setting, and show a family of DSOs that exhibits a tradeo between the additive stretch and the size of the oracle. Finally, for the meaningful single-source case, the above result is complemented by a lower bound conditioned on the Set-Intersection conjecture. This lower bound establishes a separation between the oracle and the subgraph settings. (2) FTP: We show the construction of a path-reporting DSO of size O(n4/3(|S||T|)1/3) reporting pG-e(s, t) in O(|pG-e(s, t)| + (n|S||T|)1/3) time. Such a DSO can be transformed into a FTP having the same size, and moreover it can be elaborated in order to make it optimal (up to a poly-logarithmic factor) both in space and query time for the special case in which T = V (G). Our FTP improves over previous constructions when |T| = O(|S|n) (up to inverse poly-logarithmic factors). (3) Routing and Labeling Schemes: For the well-studied single-source setting, we present a novel routing scheme, that allows to route messages on pG-e(s,t) by using edge labels and routing tables of size O(n), and a header message of poly-logarithmic size. We also present a labeling scheme for the setting which is optimal in space up to constant factors.