Student presentation # 2

(Guest post by Steve Uurtamo)

I presented the result by Omer Reingold that the decision problem of determining whether two given vertices ( and ) are connected in a given graph can be determined in space logarithmic in the size of the graph.

The approach given in the paper was to transform each connected component of the graph into an subgraph with good expansion properties (using an iterated transformation that respects the original connectivity properties), and then simply to walk the vertices of the expander starting at , either arriving at or proving that no such path exists.  Because the new graph has small diameter, it is possible to enumerate and check all such possible paths in logarithmic space.