Blackout-tolerant temporal spanners

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). We provide almost tight bounds on the size of such spanners for general temporal graphs and for temporal cliques, showing that they are either very sparse (i.e., they have delta(n) edges) or they must have size Omega(n(2)) in the worst case, where n is the number of vertices of G. We also investigate multiple blackouts and k-edge fault-tolerant temporal spanners