FAULT TOLERANT SPANNERS FOR GENERAL GRAPHS

This paper concerns graph spanners that are resistant to vertex or edge failures. In the failure-free setting, it is known how to efficiently construct a (2k - 1)-spanner of size O(n(1+1/k)), and this size-stretch trade-off is conjectured to be tight. The notion of fault tolerant spanners was introduced a decade ago in the geometric setting [C. Levcopoulos, G. Narasimhan, and M. Smid, in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 186-195]. A subgraph H is an f-vertex fault tolerant k-spanner of the graph G if for any set F subset of V of size at most f and any pair of vertices u, v is an element of V\F, the distances in H satisfy delta(H\F)(u, v) <= k center dot d(G\F)(u, v). A fault tolerant geometric spanner with optimal maximum degree and total weight was presented in [A. Czumaj and H. Zhao, Discrete Comput. Geom., 32 (2004), pp. 207-230]. This paper also raised as an open problem the question of 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(2)k(f) (vertical bar) (1) center dot n(1 vertical bar) (1/k) log(1-1/k) n). Interestingly, the stretch of the spanner remains unchanged, while the size of the spanner increases only 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(f center dot n(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.