Graph distances in the streaming model: the value of space

We investigate the importance of space when solving problems based on graph distance in the streaming model. In this model, the input graph is presented as a stream of edges in an arbitrary order. The main computational restriction of the model is that we have limited space; therefore, we cannot remember all the streamed data but rather are forced to make space-e#cient summaries of the data as we go along. For a graph of n vertices and m edges, we show that testing many graph properties, including connectivity (ergo any reasonable decision problem about distances) and bipartiteness, requires #(n) bits of space. Given this, we then investigate how the power of the model increases as we relax our space restriction. Our main result is an e#cient randomized algorithm that constructs a (2t+1)-spanner in one pass. With high probability, it uses O(t n) bits of space and processes each edge in the stream in O(t log n) time. We find approximations to diameter and girth via the constructed spanner. For t = #( ), the space requirement of the algorithm is O(npolylog n), and the per-edge processing time is O(polylog n). We also show a corresponding lower bound of t for the approximation ratio achievable when the space restriction is O(t n).