Undirected ST-connectivity in logspace

The undirected ST connectivity (USTC) problem is: given an undirected graph G=(V,E) and two vertices s,t, decide whether or not s and t are in the same connected component of G. The proof that USTC is in L (deterministic logspace) makes good use of expanders.

We first reviewed what results were known about USTC and the logspace complexity classes. It was known that USTC is complete for SL, languages accepted by nondeterministic logspace machines whose transition functions are "symmetric" in a certain sense. The directed version of ST connectivity is complete for NL, while connectivity in undirected forests is complete for L.

L ⊆ SL ⊆ NL ⊆ DSPACE(log² n)

The last inclusion is from Savitch's theorem. Showing that USTC ∈ L yields L = SL.

The algorithm for USTC proceeds roughly as follows. Given input ⟨G,s,t⟩:

1. Convert G to a regular graph G_reg in a way that preserves connected components.
   
2. Amplify G_reg's expansion properties by powering operations and taking zig-zag products appropriately (again preserving connected components). Call the result G_L.
   
3. Since G_L is a good expander, it has logarithmic diameter. Thus we can simply perform a bounded-depth DFS on this graph from s' to determine reachibility of t'.

Of course, these intermediate graphs are not computed in memory. To do the last step, we only need to be able to compute G_L's rotation map in logspace. This is possible, with recursive calls to the intermediate graphs, and finally using the original G's adjacency relation as the base case.

Converting G to G_reg: Assuming V(G) = {1, ..., n}, we perform a replacement product on G, where each vertex u is replaced with an n-cycle whose vertices are { ⟨u,v⟩ | v ∈ V(G) }. If u and v were connected in G, we connect new vertices ⟨u,v⟩ and ⟨v,u⟩. We add self-loops everywhere else so that the degree becomes D¹⁶, where D is a constant we'll define later.

We label edges in the replacement cycle as 1 & 2, and possible edges between cycles as 3. In terms of the rotation map, this looks like:

R( ⟨u,i⟩, 1 ) = ( ⟨u, (i-1)%n⟩, 2 )
R( ⟨u,i⟩, 2 ) = ( ⟨u, (i+1)%n⟩, 1 )
R( ⟨u,v⟩, 3 ) = ( ⟨v,u⟩, 3 ), if u and v are connected in G, and ( ⟨u,v⟩, 3 ) otherwise
R( ⟨u,v⟩, i ) = ( ⟨u,v⟩, i ), for i > 3

It is easy to see that this construction preserves connected components, and that this rotation map can be computed in constant space. The size of the graph increases quadratically, so logarithmic quantities in the size of G_reg are also logarithmic in G.

Converting G_reg to an expander: This operation uses powering and zig-zag operations, so let's review how these operations affect expander properties. We say a graph is (N, D, λ) if it has N vertices, is D-regular, and λ is its 2nd largest normalized eigenvalue magnitude.

1. Powering a graph (G → G^k) changes it from a (N, D, &lambda) graph to a (N, D^k, λ^k) graph.
   
2. The zig-zag product G z H, where G is a (N, D¹⁶, λ) graph, and H is a (D¹⁶, D², α) graph, results in a graph which is (ND¹⁶, D, f(λ,α)).
   
3. Combining these two operations, if we take G and H as above, the graph (G z H)⁸ is (ND¹⁶, D¹⁶, f⁸(λ,α)).

Note especially that the graph (G z H)⁸ has suitable degree for us to zig-zag it again with H.

The reason for the appearance of D¹⁶ is that it is possible to show with a probabilistic argument that there exists some constant D and a graph H which is (D¹⁶, D, 1/2). This will be the value of D we'll use, and the graph H will be a constant that is hard-coded into the algorithm.

Now, we define a sequence of graphs as follows:

• G₀ = G_reg
  
• G_i+1 = (G_i z H)⁸

It follows that G_i has ND^{16 i} vertices and degree D¹⁶. Let us now see how these operations affect the λ parameter.

Let &lambda_i be the λ parameter of G_i. Using a bound on the f() function from the zig-zag product, we inductively proved a lemma that &lambda_i < max{ (λ₀)²ⁱ, 1/2 }. In other words, the eigenvalues of the G_i sequence decrease geometrically until they reach 1/2, after which they stay below 1/2. (Actually, the argument is more subtle. We actually apply this bound to each of G_i's connected components separately, since it is only valid for connected graphs).

We also proved a lemma that for any D-regular non-bipartite graph on N vertices, its 2nd largest normalized eigenvalue magnitude is at most 1 - 1/DN². That is, every regular graph has a nonnegligable spectral gap. Our graph G₀ is non-bipartite (it has self-loops at every vertex). So combining these two observations about the eigenvalues, we see that for L = O(log N), the graph G_L has λ_L < 1/2. Its size is also polynomial in N. The graph G_L will be our final expander.

Computing G_L's rotation map in logspace:

Vertices in G_i correspond to a vertex in G_i-1 along with an edge number (which together comprise a vertex in the replacement product), and edges in G_i consist of 16 "zig-zag" edge labels (due to powering the graph to the 8th power). Once the description of such a vertex ⟨v,a⟩ and edge label ⟨i₁,...,i₁₆⟩ are written down in memory, we can compute the rotation map with very little memory overhead:

• To compute R_Gi(⟨v,a⟩, ⟨i₁,...,i₁₆⟩):
  
  • For j = 1 to 16 do:
    
  • ⟨a,i_j⟩ = R_H(a,i_j)
    
  • If i is odd, then do ⟨ v,a⟩ = R_Gi-1(v,a)

The final result is is ⟨v,a⟩, ⟨i₁₆,...,i₁⟩. Note that we use a recursive call to compute the rotation map of G_i-1, which is allowed to rewrite the memory of its argument in the same manner. Analyzing this algorithm, we see that at each level of recursion, we only need to keep track of loop variable j and our position i in the recursion, taking O(log N) space.

Putting it together:

Finally, to determine connectivity between s and t, we perform a DFS on G_L starting at a representative for s and looking for a representative of t. Since it is an expander with a constant spectral gap, it has logarithmic diameter, and we can bound our DFS to O(log N) steps without loss of generality.

To keep track of our position in the DFS, we only need to keep track of the current vertex's description, and the last edge label we traversed, which takes only O(log N) bits. The symmetric nature of the rotation map allows us to "back up" in the DFS tree. When we back up, we will have the label of the edge that was just taken from the vertex, which we can increment to recurse again (or back up again if it is this vertex's last unvisited edge).