On expander graphs and connectivity in small space

Abstract

This presentation is aimed to communicate a recently found deterministic algorithm for determining connectivity in undirected graphs [40]. This algorithm uses the minimal amount of memory possible, up to a constant factor. Specifically, the algorithm’s memory is comparable to that needed to store the name of a single vertex of the graph (i.e., it is logarithmic in the size of the graph).

Our algorithm also implies a deterministic, short (i.e. of polynomial length), universal sequence of steps which explores all the edges of every regular undirected graph. Such a sequence will get one out of every maze, and through the streets of every city. More formally we give universal exploration sequences for arbitrary graphs and universal traversal sequences for graphs with some natural restriction on their labelling. Both sequences are constructible with logarithmic memory and are thus only polynomially long.

To obtain this algorithm, we give a method to transform (using small memory), an arbitrary connected undirected graph into an expander graph (which is a sparse but highly connected graph).