Fault-tolerant spanners for general graphs

The paper concerns graph spanners that are resistant to vertex or edge failures. Given a weighted undirected n-vertex graph G = (V,E) and an integer k ≥ 1, the subgraph H = (V,E'), E'⊆ E, is a spanner of stretch k (or, a kspanner) of G if δH(u, v) k δG(u, v) for every u, v 2 V , where δG0 (u, v) denotes the distance between u and v in G' Graph spanners were extensively studied since their introduction over two decades ago. It is known how to efficiently construct a (2k-1)-spanner of size O(n^1+1/k), and this sizestretch tradeoff is conjectured to be tight. The notion of fault tolerant spanners was introduced a decade ago in the geometric setting [Levcopoulos et al., STOC'98]. A subgraph H is an f-vertex fault tolerant kspanner of the graph G if for any set F V of size at most f and any pair of vertices u, v 2 V \ F, the distances in H satisfy δH\F (u, v) ≤ k δG\F (u, v). Levcopoulos et al. presented an efficient algorithm that given a set S of n points in Rd, constructs an f-vertex fault tolerant geometric (1+ε)-spanner for S, that is, a sparse graph H such that for every set F S of size f and any pair of points u, v 2 S \F, H\F (u, v)(1+ε)|uv|, where |uv| is the Euclidean distance between u and v. A fault tolerant geometric spanner with optimal maximum degree and total weight was presented in [Czumaj & Zhao, SoCG'03]. This paper also raised as an open problem the question whether it is possible to obtain a fault tolerant spanner for an arbitrary undirected weighted graph. The current paper answers this question in the affirmative, presenting an f-vertex fault tolerant (2k-1)-spanner of size O(f²k^f+1n^1+1/k log^1-1/k n). Interestingly, the stretch of the spanner remains unchanged while the size of the spanner. only increases by a factor that depends on the stretch k, on the number of potential faults f, and on logarithmic terms in n. In addition, we consider the simpler setting of f-edge fault tolerant spanners (defined analogously). We present an f-edge fault tolerant 2k -1 spanner with edge set of size O(fn^1+1/k) (only f times larger than standard spanners). For both edge and vertex faults, our results are shown to hold when the given graph G is weighted