This post continues my series on favorite theorems of the twenty-first century. For an overview of the categories and my earlier selections, see this introductory post.
My choice for 2005 in Algorithms and Complexity is a theorem of Omer Reingold showing that connectivity in undirected graphs can be decided by a deterministic algorithm using only logarithmic memory. The result was presented at STOC 2005 (Reingold 2005), and the full paper appeared in the Journal of the ACM in 2008 (Reingold 2008).
When studying algorithms, we usually focus on their running time. However, the amount of memory required by an algorithm is another fundamental measure of its efficiency. An algorithm that runs quickly but requires enormous amounts of memory may be impractical, especially when processing very large datasets.
In complexity theory, a decision problem belongs to the class log-space, denoted by , if it can be solved by a deterministic algorithm using only bits of working memory, where is the size of the input. The input itself is stored in read-only memory and is not counted towards this bound. The algorithm may examine the input repeatedly, but it cannot modify it.
Logarithmic memory is an extremely restrictive requirement. For example, identifying a vertex in a graph with one million vertices requires only about bits. Thus, an algorithm using memory can store only a constant number of vertex labels, together with a small amount of additional information. In particular, it cannot maintain a list of all previously visited vertices.
Consider the following fundamental problem in graph theory. We are given an undirected graph with vertices and two distinguished vertices . We want to determine whether there exists a path from to , that is, a sequence of vertices such that for every .
This problem is called undirected connectivity, or undirected - connectivity.
There are elementary algorithms for solving it. For example, breadth-first search starts at and systematically explores all vertices reachable from it. If is encountered, the answer is positive; otherwise, it is negative. Such algorithms are very efficient in terms of running time, but they generally require memory proportional to the number of vertices, up to logarithmic factors.
Can we solve the same problem using only logarithmic memory?
A natural approach is to use a random walk. Start at and repeatedly move to a randomly selected neighboring vertex. If and are connected, then, with sufficiently high probability, a random walk of polynomial length will eventually visit . If they are not connected, the walk will never reach .
In 1979, Aleliunas, Karp, Lipton, Lovász, and Rackoff (Aleliunas et al. 1979) used this idea to obtain a randomized log-space algorithm for undirected connectivity. Indeed, the algorithm needs to remember only its current position and the number of steps taken, both requiring bits.
The difficulty is to remove randomness. Could one construct a deterministic sequence of moves that is guaranteed to find whenever it is reachable, without remembering which vertices have already been visited?
Reingold answered this question affirmatively.
The proof is based on the remarkable properties of expander graphs. These are graphs which have relatively few edges but are nevertheless highly connected, in the sense that every sufficiently small set of vertices has many edges leading outside it. We have discussed expander graphs and their applications in an earlier post.
An important property of expander graphs is that any two vertices can be connected by a relatively short path. For an expander with a bounded number of neighbors per vertex, the length of such a path is . Consequently, connectivity can be tested using logarithmic memory by systematically examining all possible paths of this length.
The main achievement of Reingold was to show how to transform an arbitrary undirected graph into a new graph whose connected components are expanders, while preserving the information about which vertices are connected. Crucially, this transformation can itself be carried out using only logarithmic memory.
The construction uses the zig-zag graph product, introduced by Reingold, Vadhan, and Wigderson (Reingold et al. 2002). This operation allows one to improve the connectivity properties of a graph while keeping the number of neighbors of each vertex bounded.
The result has another striking interpretation. Reingold’s method gives a way to construct a universal exploration sequence: a predetermined sequence of instructions which, when interpreted appropriately, is guaranteed to visit every vertex of any connected undirected graph of a given size. Moreover, the instructions can be generated using only logarithmic memory. Thus, it is possible to explore an arbitrary network without randomness and without maintaining a list of previously visited vertices.
Theorem also settled a long-standing question in complexity theory by establishing the equality where is the class of problems solvable using symmetric nondeterministic logarithmic-space computation.
Interestingly, the corresponding question for directed graphs remains open. Determining whether two vertices in a directed graph are connected by a directed path is a fundamental example of a problem in the complexity class , and it is still unknown whether
Although Reingold’s algorithm is primarily of theoretical interest, since simpler graph-search algorithms are usually more practical, the theorem represents a major breakthrough. It shows that a problem which apparently requires keeping track of a large amount of information can, in fact, be solved with memory barely sufficient to store the name of a single vertex.