Blackout-Tolerant Temporal Spanners

In this paper we introduce the notions of blackout-tolerant temporal -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, 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.,), almost-exact distances (i.e., for an arbitrarily small constant), and connectivity (i.e., unbounded). 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-spanner for both general temporal graphs and for temporal cliques. Our result show that such spanners are either very sparse (i.e., they have edges) or they must have size 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.