Paper Info
Title
Efficient Oracles and Routing Schemes for Replacement Paths.
Abstract
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 pi(G)(-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) is an element of S x T, where S, T subset of V(G), and every e is an element of E(G), maintain the collection of all pi(G)(-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 subset of V(G), we construct a DSO for maintaining S x T distances under single edge (or vertex) faults. This DSO has size (O) over tilde (n root vertical bar S parallel to T vertical bar) and query time of O(root vertical bar S parallel to T vertical bar). At the expense of having quasi-polynomial query time, the size of the oracle can be improved to (O) over tilde (n vertical bar S vertical bar + vertical bar T vertical bar root vertical bar S vertical bar n), which is optimal for vertical bar T vertical bar = Omega(root n vertical bar S vertical bar). When vertical bar T vertical bar = Omega (n(3/4)vertical bar S vertical bar(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 tradeoff 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) over tilde (n(4/3)(vertical bar S parallel to T vertical bar)(1/3)) reporting pi(G-e)(s,t) in O(vertical bar pi(G-e)(s,t)vertical bar + (vertical bar S parallel to T vertical bar)(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 vertical bar T vertical bar = O (root vertical bar S vertical bar 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 pi(G)(-e)(s,t) by using edge labels and routing tables of size (O) over tilde(root 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.
Year
DOI
Venue
2018
10.4230/LIPIcs.STACS.2018.13
Leibniz International Proceedings in Informatics
Keywords
Field
DocType
Fault Tolerant,Shortest Path,Oracle,Routing
Discrete mathematics,Inverse,Combinatorics,Vertex (geometry),Polynomial,Computer science,Upper and lower bounds,Oracle,Omega,Routing table,Conjecture
Conference
Volume
ISSN
Citations 
96
1868-8969
0
PageRank 
References 
Authors
0.34
0
6
Name
Order
Citations
PageRank
Davide Bilò118021.23
Keerti Choudhary2378.81
Luciano Gualà312119.25
Stefano Leucci48315.33
Merav Parter516932.59
Guido Proietti653267.65