Computing Graph Spanners in Small Memory: Fault-Tolerance and Streaming

Let G be an undirected graph with m edges and n vertices. A spanner of G is a subgraph which preserves approximate distances between all pairs of vertices. An f-vertex fault-tolerant spanner is a subgraph which preserves approximate distances, under the failure of any set of at most f vertices. The contribution of this paper is twofold: we present algorithms for computing fault-tolerant spanners, and propose streaming algorithms for computing spanners in very small internal memory. In particular, we give algorithms for computing f-vertex fault-tolerant (3,2)- and (2,1)-spanners of G with the following bounds: our (3,2)-spanner contains O(f(4/3)n(4/3)) edges and can be computed in time (O) over tilde (f(2)m,), while our (2,1)-spanner contains O(fn(3/2)) edges and can be computed in time (O) over tilde (fm). Both algorithms improve significantly on previously known bounds. Assume that the graph G is presented as an input stream of edges, which may appear in any arbitrary order, and that we do not know in advance m and n. We show how to compute efficiently (3,2)- and (2,1)-spanners of G, using only very small internal memory and a slow access external memory device. Our spanners have asymptotically optimal size and the I/O complexity of our algorithms for computing such spanners is optimal up to a polylogarithmic factor. Our f-vertex fault-tolerant (3,2)- and (2,1)-spanners can also be computed efficiently in the same computational model described above.