Blackout-Tolerant Temporal Spanners

In this paper we introduce the notions of blackout-tolerant temporal alpha-spanner of a temporal graph G which is a subgraph of G that preserves the distances between pairs of vertices of interest in G up to a multiplicative factor of alpha, even when the graph edges at a single time-instant become unavailable. In particular, we consider the single-source, single-pair, and all-pairs cases and, for each case we look at three quality requirements: exact distances (i.e., alpha = 1), almost-exact distances (i.e., alpha = 1+ epsilon for an arbitrarily small constant epsilon > 0), and connectivity (i.e., unbounded alpha). For each combination we provide tight bounds, up to polylogarithmic factors, on the size, which is measured as the number of edges, of the corresponding blackout-tolerant a-spanner for both general temporal graphs and for temporal cliques. Our result show that such spanners are either very sparse (i.e., they have (O) over tilde (n) edges) or they must have size Omega(n(2)) in the worst case, where n is the number of vertices of G. To complete the picture, we also investigate the case of multiple blackouts.