\documentclass[12pt]{article}
\newtheorem{define}{Definition}

%\newcommand{\Z}{{\mathbb{Z}}}

\usepackage{psfig}
\usepackage[dvips]{color}
\usepackage{epsfig}
\usepackage{algorithm2e}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{18}{April 24, 2006}{Ronitt Rubinfeld}{Elena Grigorescu}

%Today we will present a recent result of Reingold, which establishes that undirected s-t connectivity can be solved in logarithmic space.

In this lecture we present the relatively recent fundamental result of O. Reingold \cite{Rei} which establishes that undirected st-connectivity can be decided in deterministic logarithmic space. 
 \\
Given an undirected graph $G$, two vertices $s$ and $t$ in $G$, USTCON$(G, s, t)$ is the problem of deciding whether 
there exists a path in $G$ connecting $s$ and $t$. 
The more difficult, directed graph version of this problem is known to be NL-complete, and thus in $L^2$ by Savitch's theorem. Prior to the Reingold result, USTCON was known to be in RL \cite{AKL}, and later (\cite{ATS}) in $\log^{4/3}.$ Also, USTCON
is a complete problem for the mysterious class SL (symmetric, non-deterministic, log space computations), and therefore
USTCON$\in$ L implies SL=L.
\\\\
We will start by introducing some notation and recalling some results from previous lectures/homeworks.


\begin{definition}
A $(N, D, \lambda)$-graph is an undirected graph on $N$ vertices, of degree $D$, and with the second largest eigenvalue bounded above by $\lambda$.
\end{definition}

The relationship between the second eigenvalue and that of vertex expansion is given in the following proposition. 
\begin{proposition} \label{expansion}
 Let  $\lambda <1$. Then  $\exists \varepsilon>0$ s.t. for  any $(N, D,  \lambda)$-graph $G$,  
$ \forall S \subset V, \mbox{ s.t. } |S|<\frac{N}{2}$ we have that $|N(S)|\geq (1+\varepsilon)|S|.$ In this case we say that $G$ is an {\it expander. Note:  Elements of $S$ may be in $N(S)$}
\end{proposition}

\begin{corollary}
If $\lambda<1$, then for every connected graph $(N, D, \lambda)$, there exists a path of length $O(\log N)$ between any vertices $s$ and  $t$. In particular, $G$ has $O(\log N)$ diameter. 
\end{corollary}

\begin{proof}
By the vertex expansion property given in  Proposition \ref{expansion}, it follows that starting at $s$ and successively following the neighboring sets for $l=O(\log N)$ steps we must have covered $>N/2$ of the vertices. Repeating the process from vertex $t$, it must be the case that there is a vertex reached from both $s$ and $t$ in these $l$ steps.
\end{proof}

For and expander graph $G$ of constant degree, one can now easily check st-connectivity in $\log N$ space as follows:
\begin{itemize}
\item Enumerate all $D^l$ paths starting at $s$ of length $l=O(\log N)$.
\item If have reached node $t$ then output `connected', else output `not connected'.
\end{itemize}

Notice that the space requirement of the algorithm is $O(\log{ N }\log{ D}$, which is $O(\log N)$ for constant $D$.
We will reduce the problem of checking st-connectivity in a general graph, to that of checking st- connectivity in an expander graph with constant degree $D$. \\

{\bf Observation:} The results shown in this lecture do not apply to general directed graphs. However, for the special case of directed graphs with constant out-degree equal to the in-degree at each vertex, similar results do hold.\\

A key fact that will be relevant to the main proof states that the spectral gap ($1-\lambda(G)$) of any connected, non-bipartite graph $G$ is large enough, namely at least inverse polynomial in $|G|$, as described next.

\begin{theorem}\label{general_lambda}
For any connected $D$-regular and non-bipartite graph $G$ the following holds
$$\lambda(G)\leq 1-\frac{1}{DN^2}.$$
\end{theorem}

We further add to our toolkit a useful graph.
\begin{theorem}\label{tool}
There exist a constant $D_e$ and a $(D_e^{16}, D_e, \frac{1}{2})$-graph.
\end{theorem}


Also, recall that the graph powering operation is a simple method of increasing the connectivity of a graph.

\begin{proposition} (Graph powering)
If $G$ is a $(N, D, \lambda)$-graph, then the power $G^t$ of $G$ is a $(N, D^t, \lambda^t )$-graph. 
\end{proposition}

\noindent{\bf Observation:} Notice that graph powering increases a lot the degree of the new graph. In particular, for a good enough $\lambda$ we will want $t=O(\log N)$, while we only aim for $t=constant$. Reingold's proof
does use manipulations of graphs using this operation. However, his main ingredient  is a new operation (the {\bf zig-zag product}) that will bring down the degree of the graph, while increasing $\lambda$ by only a small constant factor. \\
 
 A simple example of a way to lower the degree of a graph is shown in the picture below, where a node is substituted by a cycle.
\begin{figure}[h]\label{lessdeg}
\begin{center}
\epsfxsize=45mm
\epsfbox{lessdeg.eps}
\end{center}
\end{figure}
 
We next introduce two graph products that have the property that they reduce the degree of a graph while not increasing $\lambda$ by too much either. 
\\
\noindent{\bf Replacement product: }\\
Given graph an $(N, D)$  graph $G$ and a $(D, d)$ graph $H$, the replacement product graph $G'$ is obtained from $G$ and $H$ in the following way:
\begin{itemize}
\item Each node $v\in G$ is replaced by a copy of $H$, called $H_v$. Thus, there are $N~D$ nodes in $G'$.
\item Each node $v'\in H_v$ corresponds to an edge from $v\in G$. Therefore, $v'\in H_v$ is adjacent to the $d$ nodes in $H_v$ and to a vertex in $H_z$, where $(v, z)\in E(G)$ and $v'$ corresponds to $z$. Therefore, $v'$ has degree $d+1<<D$. 
\end{itemize}

\begin{figure}[h]\label{zigzag}
\begin{center}
\epsfxsize=75mm
\epsfbox{zigzag.eps}
\end{center}
\end{figure}

\noindent{\bf Zig-zag product:}\\
The zig-zag product $G''$ of $G$ and $H$ (notation $GzH$), where $G$ is $~D$-regular and has $N$ nodes and $H$ is $~d$-regular and has $D$ nodes is constructed from the replacement product $G'$ of $G$ and $H$:
\begin{itemize}
\item  $V(G'')=V(G')$.
\item The edges of $G''$ are between vertices $x, w\in G'$ that are connected by a path of length three, that starts in 
$x\in H_v$, takes a step $ (x, y)\in E(H_v)$, then follows the edge $(y, z)\in G$, where $z\in H_w$, and finally, takes a step $(z, w)\in E(H_w)$. Therefore, the degree of each vertex is $d^2$.
\end{itemize}


Next we state one of the main tools of the proof, namely the relationship between the second eigenvalues of the graphs $G$ and $H$ to the second eigenvalue of the zig-zag product of $G$ and $H$. 
\begin{theorem}(\cite{RVW})
Let $G$ be a $(N, D, \lambda)$-graph, and $H$ be a $(D, d, \alpha)$-graph.
Then $GzH$ is a $(N D, d^2, f(\lambda, \alpha))$-graph, where 
$f(\lambda, \alpha)=\frac{1}{2}(1-\alpha^2)\lambda+\frac{1}{2}\sqrt{ (1-\alpha^2)^2\lambda^2+4\alpha^2}$.
\end{theorem}

In fact, a nicer form of this theorem will be enough for our purposes. The following corollary shows that the spectral gap of the zig-zag product is only larger by a small factor from the spectral gap of $G$.  

\begin{corollary}\label{spectral_relation}
For $G, H$ as above, 
$$\frac{1}{2}(1-\alpha^2)(1-\lambda)\leq 1- \lambda(G z H).$$
\end{corollary}

We are now ready for the final construction of the expander graph that we are after.
\begin{algorithm}
{\bf Main Transformation:}

{\bf Given:} $G$ that is $D^{16}$-regular on $N$ vertices,\\
and $H$ that is $D$-regular on $D^{16}$ vertices (given by Theorem \ref{tool}),\\
Let $l$ be the smallest integer s.t. $(1-\frac{1}{DN^2})^{2^l}<\frac{1}{2}.$\\
Let $G_0\leftarrow G$\\
Let $G_i\leftarrow (G_{i-1} z H)^8$\\
{\bf Output:} $\tau(G, H)=G_l$.
\end{algorithm}

Observation: The number of nodes in $G_l$ is $N (D^{16})^l =\poly(N)$, since $l=O(\log N)$.


\begin{lemma}
If $H$ is an expander, then $G_l$ is an expander. Equivalently, if $\lambda(H)\leq \frac{1}{2}$ and $G$ is connected and not bipartite, then $\lambda(\tau(G, H))\leq \frac{1}{2}$. 
\end{lemma}

\begin{proof}[Sketch]
By Theorem \ref{general_lambda} we have that $\lambda(G_0)\leq 1-\frac{1}{DN^2}$. 
Notice that it is enough to show inductively that $\lambda(G_i)\leq \max\{\lambda(G_{i-1})^2, \frac{1}{2})\}.$ This will imply that, for $l=O(\log(N)\log(D))$ we have that $\lambda(G_l)\leq \max\{\lambda(G_0)^{2^l}, \frac{1}{2}\}<\frac{1}{2}.$ 
To prove the induction hypothesis, notice that $\lambda(H)\leq \frac{1}{2}$. By Corollary \ref{spectral_relation}, we have that $\lambda(G_{i-1} zH)< 1- 1/3 ~(\lambda(G_{i-1}).$ Therefore, $\lambda(G_i)< (1- 1/3 ~(\lambda(G_{i-1}))^8$. 
The conclusion follows then by elementary calculations, by considering the cases $\lambda(G_{i-1})< 1/2$, and $\lambda(G_{i-1})\geq 1/2$

\end{proof}

\noindent We next present an overview of the actual $\log N$ space algorithm solving st-connectivity. 

\begin{algorithm}[H]
1. Preprocessing stage: make the graph $G$ $~D^{16}$ regular, preserving non-bipartiteness, and the connected components. This can be done by the replacement product of $G$ with an $N$-cycle and then adding self-loops. Note that the number of nodes becomes $N^2$ but this operation is performed only once. Let $G_e$ be the resulting graph.\\
2. Use the transformation $\tau$ described before on the preprocessed graph $G_e$ and $H$ the expander given by  Proposition \ref{tool}.\\
3. Run the expander algorithm on $\tau(G_e, H)$. 
\end{algorithm}


 The only tricky part that one needs to verify now is how  the walks are performed in $\log$ space. 
The choice of representing  graphs $G$ and $H$ as so-called {\it rotation maps} turns out to be fortunate.
This representation implies that  each edge is labeled at both its endpoints, which gives a way of tracing a path back from any position by only remembering a constant number of labels. 

\begin{definition}\cite{Rei}
For a $D$-regular undirected graph $G$, the {\bf rotation map} $Rot_G: [N]\times [D] \rightarrow [N]\times [D]$ is defined as $Rot_G(v, i)=(w, j)$ if the $i$' th edge incident to $v$ leads to $w$, and this edge is also the $j$'th edge incident to $w$.
\end{definition}

It follows easily that given the rotation map of $G$ one can compute in $\log N$ space the rotation map of $G_e$.
The heart of the problem is showing that the rotation map of $\tau(G_e, H)$ is computable in $\log$ space given the rotation maps of $G$ and $H$. The proof uses an inductive argument and elementary techniques, and we do not attempt it here.

\bibstyle{alpha}
     \begin{thebibliography}{99}
     \bibitem{AKL} Aleliunas, Karp, Lipton, Lovasz, Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. {it Annual Symposium on Foundations of Computer Science}. 1979.
     \bibitem{ATS} Armoni, Ta-Shma, Wigderson, Zhou. An $o(log(n)^{4/3})$ space algorithm for st-connectivity in undirected graphs. JACM, 2000.
\bibitem{Rei} O. Reingold. Undirected st-connectivity in Log Space. 2004.
\bibitem{RVW} O. Reingold, S. Vadhan, A. Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders. FOCS 2000.
\end{thebibliography}
\end{document}