\documentclass{article}
\pagestyle{plain}
\newtheorem{define}{Definition}
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}
\usepackage{changepage}
\usepackage{caption}
\usepackage{wrapfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage{xcolor}
\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{19}{April 22, 2019}{Ronitt Rubinfeld}{William Loucks}

%%%% body goes in here %%%%

\section{Graph Spanners}

\begin{definition} Given undirected graph $G = (V,E)$, a \textbf{k-spanner} is a subgraph $H = (V, E')$ such that $E' \subseteq E$ and $\forall u,v \in V$, $dist_{H}(u,v) \leq k \cdot dist_{G}(u,v)$
\end{definition}

\noindent Equivalently, one could state that $\forall (u,v) \notin H$ (edges therein), there exists a path from $u$ to $v$ in $H$ of length less than $k$, also known as the \textit{stretch}. We know that optimal $(2k-1)$-spanners obtain $O(n^{1+1/k})$ edges for $k = 2,3,$ and $5$. Further, assuming the Erdos Girth Conjecture, for all $k$, there exists $G$ for which any $(2k-1)$-spanner must have $O(n^{1+1/k})$ edges.

\section{LCA for 3-Spanner}

Today, we show a 3-spanner with $\widetilde{O}(n^{3/2})$ edges and a probe complexity of $\widetilde{O}(n^{3/4})$. Note, the complexity varies based on whether or not one wishes to minimize the query complexity or the number of edges.

\noindent We assume the following probes with complexity $O(1)$ to graph $G$:
\begin{enumerate}
	\item \textit{Neighbor:} Given $u,i$, output the ith neighbor of $u$
	\item \textit{Adjacency:} Given $(u,v)$, output $j$ if $(u,v) \in G$ and where $v$ is the jth neighbor of of $u$; output ``no" otherwise
	\item \textit{Degree:} Given $u$, output $deg(u)$
\end{enumerate} \ \\

\noindent First, consider a thought: pick a random center and if $u$ and $v$ are connected to the same center, delete the edge $(u,v)$. Then $dist_{G}(u,v) = 1$ and $dist_{H}(u,v) = 2$, permissible for a 3-spanner. 
\begin{figure}[h]
	\centering
	\includegraphics[width=0.25\linewidth]{fig1}
	\caption{$u$ and $v$ connected to the same center, can delete $(u,v)$}
	\label{fig:fig1}
\end{figure}

\noindent However, we may not delete \textit{enough} edges this way, and it may be difficult to determine -- in sublinear time -- that $u$ and $v$ are connected to the same center.

\subsection{Global Construction of 3-Spanners [Baswana Sen '07]}

\noindent Construction of $H$:

\begin{itemize}
	\item Pick $S \subseteq V$ such that $|S| = \Theta(\sqrt{n}\cdot \log(n))$. In other words, each node tosses a coin with bias $\Theta(\frac{\log(n)}{\sqrt{n}})$. These form the \textit{cluster centers}.
	\item With high probability, $\forall u \in V$ such that $u$ has degree greater than $\sqrt{n}$, $u$ is adjacent to at least one center $v \in S$. Ultimately, $u$ chooses only one $v \in S$ to be its cluster center.
\end{itemize}

\noindent Further, to construct $H$ we comply with the following rules:
\begin{enumerate}
	\item If $u$ has low degree $(< \sqrt{n})$, then add all edges $(u,v)$
	\item If $u$ has high degree $(\geq \sqrt{n})$, then add edge $(u,v)$ to cluster center
	\item If $u$ has high degree $(\geq \sqrt{n})$, add \textbf{one} edge to \textbf{every} adjacent cluster 
\end{enumerate}

\noindent Given the above, step 1 results in at most $n \cdot \sqrt{n}$ edges; step 2 adds at most $n$ edges; and step 3 results in at most $n \cdot \sqrt{n} \cdot \log(n)$ edges. Thus, the overall edge count obtains $\widetilde{O}(n^{3/2})$.

\begin{figure}[h]
	\centering
	\includegraphics[width=.35\linewidth]{fig2}
	\caption{Example constructing $H$ given the above rules. Clusters circled for illustration.}
	\label{fig:fig2}
\end{figure}

\noindent Note, for $u$ and $v$ in the same cluster, both nodes kept their edges to the cluster center. Thus, $dist_{H}(u,v) = 2$. Moreover, for $u$ and $v$ in different clusters: if $(u,v) \notin H$, the nodes must have kept some other edge $(u,w)$ such that $w$ is in $v$'s cluster. Thus, either $w$ is $v$'s center, or $(u,w), (w,c_{v}), (c_{v}, v) \in H$ yielding $dist_{H}(u,v) = 3$.

\subsection{Local Algorithms for Constructing H}

\noindent Given $(u,v) \in G$, is $(u,v) \in H$?

\begin{enumerate}
	\item If $u$ or $v$ have low degree, then yes.
	\item  If $u$ is $v$'s center, then yes. Equivalently, if $v$ is $u$'s center, then yes.
	\item If $(u,v)$ is a chosen edge from $u$ to $v$'s cluster or from $v$ to $u$'s cluster, then yes. 
\end{enumerate}

\noindent Considering the above, for rule 1, we just use two \textit{degree} probes. However, implementing rules 2 and 3 require additional effort. We first illustrate a naive approach and then depict a less complex alternative. \\

\noindent A naive first attempt may be to choose the first node, $w$, which connects to each center in $u$'s incidence list. Implementing rules 2 and 3 could then be as follows: \ \\ \\ \\ \\

\noindent\textbf{Rule 2:}
\begin{itemize}
	\item Check if $v$ is a center
	\item Check if any node preceding $v$ on $u$'s incidence list is a center
\end{itemize}

\noindent This results in overall complexity $O(\text{max degree})$, but we can do better. Namely, $O(\sqrt{n})$ by our observation earlier that if $u$ has degree greater than $\sqrt{n}$, then $u$ is adjacent to at least one center with high probability. \ \\

\noindent\textbf{Rule 3:}
\begin{itemize}
	\item Locate $v$'s cluster center, $c_{v}$
	\item Check if any neighbors of $c_{v}$ come earlier in $u$'s incidence list.
\end{itemize}

\noindent The resultant complexity is $O(n)$, since we take $O(\sqrt{n})$ to ensure $c_{v}$ is the selected neighbor's center and $\Omega(\sqrt{n})$ to determine if the selected neighbor is earlier in $u$'s incidence list. \\

\noindent The following are improved plans to test rules 2 and 3: \\

\noindent\textbf{\textit{Improved} Rule 2:} $u$ chooses all centers in the first $\sqrt{n}$ locations of the incidence list:
\begin{center}
	$c_{u} = \{v | \text{ }v\text{ is in the first } \sqrt{n} \text{ locations of }u\text{'s incidence list and }v\text{ is a center}\}$
\end{center}

\noindent Note, with high probability, $1 \leq |c_{u}| \leq \log(n)$ if $deg(u) \geq \sqrt{n}$ \ \\

\noindent Now,
\begin{itemize}
	\item Check if $v$ is a center
	\begin{enumerate}
		\item Invoke an \textit{adjacency} query to determine $v$'s location in $u$'s incidence list
		\item Check if $v$ is a center
	\end{enumerate}
	\item Check the first $\sqrt{n}$ locations in $u$'s list to determine which are centers.
\end{itemize}

\noindent Now, we can use one \textit{adjacency} probe to determine if $u$ is $v$'s center and, if needed, $\sqrt{n}$ \textit{neighbor} probes to find another center. \ \\

\noindent\textbf{\textit{Improved} Rule 3:} $u$ chooses the first edge which introduces $u$ to $v$'s cluster.
\begin{itemize}
	\item Locate the cluster centers, $C_{v}$
	\item For each neighbor $x$ of $u$ up to $v$:
	\begin{itemize}
		\item For each $w \in C_{v}$:
			\subitem If $w$ is a center of $x$, then cross off $w$
		\item If any $w \in C_{v}$ not crossed off, then keep $(u,v)$ in $H$
		\item Else, discard.
	\end{itemize}
\end{itemize} 

\noindent In the end, we used $\sqrt{n}$ neighbor probes to compute the set of cluster centers. Further, for each neighbor of $u$, $deg(u)$, we iterated over the number of cluster centers, $O(\log(n))$, and invoked one \textit{adjacency} query, $O(1)$, to determine if any cluster center was the center for a given neighbor. Assuming the max degree to be $O(n^{3/4})$, the overall complexity of this implementation to check rule 3 obtains $\widetilde{O}(n^{3/4})$.

 













\end{document}