%%%%%
\documentclass[10pt]{article}
\usepackage{amstext,epsfig,color}
\input{preamble.tex}
%%%%%
\oddsidemargin=0.15in \evensidemargin=0.15in \topmargin=-.5in
\textheight=9in \textwidth=6.25in
%%%%%
\newcommand{\qedsymb}{\hfill{\rule{2mm}{2mm}}}
\renewenvironment{proof}{\begin{trivlist} \item[\hspace{\labelsep}{\bf \noindent Proof.\/}] }{\qedsymb\end{trivlist}}%

\begin{document}
\lecture{4}{November 9, 2009}{Ronitt Rubinfeld}{Mille Gandelsman}


\section*{Sublinear time algorithm for maximal matching}
\subsection*{Reminder}

Last time we described the implementation of the oracle for the greedy sequential algorithm for finding maximal matching in a graph $G=(V,E)$. Such an oracle uses random numbers  
$\{r_{e}\}_{e\in E}$ assigned to each of the edges as follows:
\paragraph*{Oracle implementation\protect \\
}
Given an edge $e$, for every $e'$ neighboring $e$
of smaller rank than $e$, recursively check if $e'\in M$:
\begin{itemize}
\item if yes: return ''$e\notin M$''
\item else: continue.
\item if no neighboring $e'$ (of smaller rank) in $M$, return ``$e \in M$''
\end{itemize}
Concretely, the algorithm itself is as follows:
\begin{itemize}
\item assign $r_{e}\in_{r}[0,1]$ to each edge $e\in E$ for the use of the oracle.
\item run the oracle reduction algorithm on a set $S$ of $\Theta(\frac{1}{\epsilon^2})$ randomly picked edges, set $X_{e}=1$ if oracle says $e\in M$ and $X_{e}=0$ otherwise.

\item return $\frac{m}{|S|}\sum_{e\in S}X_{e}+\frac{\epsilon}{2}m$, where $m$ denotes the total number of edges in the graph. 
\end{itemize}

Recall the recursion description (that appears in the scribe notes of the last lecture),  and note the number of edges on which we recurse. It specifically means that we recurse only on lower numbered edges. 

\paragraph*{Correctness\protect \\
}

The correctness follows directly from the correctness of the naive greedy algorithm, as the described algorithm is just a variant of the latter.

\paragraph*{Running time analysis\protect}

\begin{claim} \textit{The expected number of queries to graph to handle a single oracle query is} $2^{O(d)}$\end{claim} 
There are $O(\frac{1}{\epsilon^2})$ turns to the oracle, so the next claim using the above is immediate:
\begin{claim}$E[\textit{total number of queries}]\leq\frac{1}{\epsilon^2}2^{O(d)}$\end{claim}

\paragraph*{Proof of claim 1\protect \\
}
$Pr[\textit{given path of length $k$ is explored}]=Pr[\textit{ranks of edges in path are decreasing}]=\frac{1}{k!}$
\newline On the other hand, the number of paths of length $k$ $\leq d^k$, and therefore:
$E[\textit{number of vertices explored in the tree}]\leq \sum_{k=0}^{\infty}\frac{d^k}{k!}\leq e^d$, meaning that: $E[\textit{query complexity}] = O(de^d) = 2^{O(d)}$,
as required.

\paragraph*{Comments\protect}
\begin{itemize}
\item We don't have to allocate $r_{e}$ for all edges in advance. Rather, we can hold a data structure (for instance: binary search tree for the edges using their $r_{e}$'s as keys) and check each time we encounter an edge $e$ whether generated such $r_{e}$ already exists. We will generate a new value $r_{e}$ only if it wasn't already generated. 
\item The algorithm in this sense is very sublinear, meaning that for most of the edges we will not generate the value $r_{e}$.
\end{itemize}


\section*{Approximating the average degree of a graph}
Given a simple graph $G=(V,E)$ (meaning - no self loops and no parallel edges), we will denote for every vertex $v\in V$: $d(v)=deg(v)=\textit{no. of $v$'s neighbors}$

\begin{definition}
[The average degree of a graph]\textit{The average degree of a graph $G=(V,E)$, denoted by $\overline{d}$ is: $\overline{d}=\frac{1}{|V|}\sum_{v\in V} d(v)$
}
\end{definition}

We will use two types of queries for the algorithm:\begin{itemize}
\item Degree query: given $v\in V$ output $d(v)$. 
\item Neighbor query: given $v\in V$ and some integer $i\in N$ output the $i-th$ neighbor of $v$.
\end{itemize}
The straightforward algorithm will naturally look like this: Pick $s$ nodes $v_{1},v_{2},...,v_{s}\in V$, and output $\frac{1}{s}\sum_{i=1}^{s}d(v_{i})$. The following problem rises in the naive analysis of this algorithm: for each vertex $v_{i}\in V$ it holds that $0\leq d(v_{i}) \leq n$ where $n=|V|$, so in order to estimate the average degree using (for instance) Chernoff bound, without assuming anything else about the numbers, we need $\Omega (n)$ samples. However, we'll see that since the $d_{i}$'s come from the degrees of a graph, the estimates can actually be much better. Note that the algorithm itself is not necessarily so bad, it is just that the analysis described is bad.

The problem is well demonstrated in the example of the following two graphs:
\begin{itemize}
\item $G_{1}=(V_{1},E_{1})$ where $V_{1}=\{v_{1}^{1},v_{1}^{2},...,v_{1}^{k}\}$ and $E_{1}=\{(v_{1}^{1},v_{1}^{2}),(v_{1}^{3},v_{1}^{4}),...,(v_{1}^{k-1},v_{1}^{k})\}$ - the graph with disjoint $\frac{k}{2}$ edges.
\item $G_{2}=(V_{2},E_{2})$ where $V_{2}=\{v_{2}^{1},v_{2}^{2},...,v_{2}^{k}\}$ and $E_{2}=\{(v_{2}^{1},v_{2}^{2}),(v_{2}^{1},v_{2}^{3}),...,(v_{2}^{1},v_{2}^{k})\}$ - the ``''star'' graph, with $k-1$ edges.
\end{itemize} 
$\overline{d}(G_{1})=1$ whereas $\overline{d}(G_{2})=2$, something that it will be impossible for the naive algorithm to distinguish without sampling $\Omega(n)$ vertices. There two questions we should ask ourselves are therefore: 
\begin{itemize}
\item If we can accept a mistake factor $2$, is it enough to use degree queries? 
\item If we would like a better approximation, how and how much can neighbor queries help?
\end{itemize}  
The first idea of the sublinear algorithm is to group vertices into buckets with similar degrees. Note that each bucket will have low variance.

\subsection*{Definitions}
\begin{itemize}
\item $\beta=\frac{\epsilon}{c}$ for $c>1$. 
\item $l$ is a lower bound for $\overline{d}$.
\item Bucketing - define $B_{i}$ as: $B_{i}=\{v|(1+\beta)^{i-1}<d(v)\leq (1+\beta)^i\}$ for $i=0,...,t-1$ where $t$ is an upper bound on $log_{(1+\beta)^n}+1$; $B_{-1}=\{v|d(v)=0\}$.
\item $n=|V|$.
\end{itemize}

\subsection*{Algorithm description}
Sample some $S\subseteq V$, for each bucket $B_{i}$ denote: $S_{i}=S\cap B_{i}$, and set $\gamma_{i}$ as follows: \begin{itemize}
\item if $S_{i}$ is ``large'', meaning that $|S_{i}|\geq \frac{1}{t}\sqrt{\frac{\epsilon}{6}\frac{l}{n}}$: $\gamma_{i}=\frac{|S_{i}|}{|S|}$ which is our approximation for $\frac{|B_{i}|}{n}$.
\item otherwise: set $\gamma_{i}=0$.
\end{itemize}
Output: $\sum_{i}\gamma_{i}(1+\beta)^{i-1}$. \newline \newline Recall that $(1+\beta)^{i-1}$ is the lower bound on the degree of some vertex $v\in B_{i}$.
Assuming that for every $i$: $\frac{|S_{i}|}{|S|}\leq \frac{|B_{i}|}{n}(1+\rho)$ for some $\rho$, we get that: \newline
$\sum_{i}\gamma_{i}(1+\beta)^{i-1}\leq \sum_{i}\frac{|S_{i}|}{|S|} (1+\beta)^{i-1} \leq \frac{|B_{i}|}{n} (1+\beta)^{i-1} (1+\rho) \leq \overline{d}(1+\rho)$
\newline where the first inequality is true because some of the $\gamma_{i}$'s equal to $0$, the second is simply our assumption, and the third uses the definition of $B_{i}$.
\newline Let us now try to determine how much could we underestimate the value of $\overline{d}$, there are three pairwise disjoint sets of edges $e=(u,v)$:
\begin{itemize}
\item $E_{1}=$ edges $(u,v)$ s.t. both $u$ and $v$ are in some large $B_{i}$; such edges are counted twice in the algorithm.
\item $E_{2}=$ edges $(u,v)$ s.t. $u$ is in some large $B_{i}$, whereas $v$ is in some small $B_{i}$; such edges are counted once in the algorithm.
\item $E_{3}=$ edges $(u,v)$ s.t. both $u$ and $v$ are in some small $B_{i}$; such edges are not counted in the algorithm at all.
\end{itemize}
It holds that: $E=E_{1}\cup E_{2}\cup E_{3}$. By our choice of the cutoff for deciding which $B_{i}$'s are large we guarantee that $|E_{3}|\leq O(\epsilon n)$
so: $\sum_{i} \gamma_{i}(1+\beta)^{i-1} \geq \frac{d}{2}\frac{1-\rho}{1+\beta}-\epsilon$ (the total number of vertices in small buckets is $O(\sqrt{\epsilon n})$ which implies that the total number of edges in $E_{3}$ is about $O(\sqrt{\epsilon n}\textit{ over } 2) = O(\epsilon n)$).
\begin{claim} \textit{Sample size of $\frac{n}{\sqrt{\epsilon n}} = \sqrt{\frac{n}{\epsilon}}$ gives $(2-O(1))$ approximation of $\overline{d}$}\end{claim} 
The claim is straightforward conclusion from the above discussion.


\subsection*{Full scale algorithm description}
The full scale algorithm uses also the random neighbors queries as follows: 
For large bucket $i$, denote by $\alpha_{i}$ the fraction of edges from $E_{2}$ hanging off bucket $i$. The lower bound on the average degree of the edges in $B_{i}$ is $(1+\alpha_{i})\gamma_{i}(1+\beta)^{i-1}$, where the $\alpha_{i}$ is added to make up for the edges from $E_{2}$ that were not seen in small buckets.

\subsubsection*{How to approximate $\alpha_{i}$}
For every vertex in a large $S_{i}$, we pick a random neighbor and set $X_{i}$ as follows:
$X_{i}=1$ if the neighbor is in some small $S_{j}$ and $X_{i}=0$ otherwise.
If all vertices in $B_{i}$ would have had the same degree then we could choose a vertex uniformly at random from $B_{i}$, here two vertices have nearly the same degree (concretely - up to $(1+\beta)$). Denote: $p=Pr[\textit{edge slot of $S_{i}$ is picked}]$. For an edge $(u,v)$ such that $u\in B_{i}$ the probability to pick an edge is $\frac{1}{|B_{i}|}\frac{1}{d(u)}$ so: 
$\frac{1}{\#S_{i}'s \textit{ edge slots}}\frac{1}{1+\beta}\leq p\leq\frac{1}{\#S_{i}'s \textit{ edge slots}}(1+\beta)$ where by edge slot we mean the number of vertices of the edge that are in the bucket.  
\newline The full scale algorithm will look like this: 
\begin{itemize}
\item set $S=\Theta(\sqrt{\frac{n}{l}}\epsilon^{-\frac{4}{5}}log^2(n)log(\frac{1}{\epsilon}))$ sampled vertices.
\item set $S_{i}=S\cap B_{i}$.
\item if $S_{i}$ is large, i.e. $\frac{|S_{i}|}{|S|} \geq \frac{1}{t}\sqrt{\frac{\epsilon}{6}\frac{l}{n}}$ use $\frac{|S_{i}|}{|S|}$ to approximate $\frac{|B_{i}|}{n}$, setting: $\gamma_{i}=\frac{|S_{i}|}{|S|}$.
\item for every large bucket $i$ and for every $v\in S_{i}$: pick random neighbor $u$ of $v$ and set $X_{v}$ as follows: 
$X_{v}=1$ if $u$ is in some small bucket and $X_{v}=0$ otherwise.
\item for every large bucket $i$: set $\overline{\alpha_{i}}=\frac{|\{v\in S_{i}|X_{v}=1\}|}{|S_{i}|}$.
\item Output $\frac{1}{|S|}\sum_{i\in\{j|\textit{j is a large bucket index}\}}(1+\overline{\alpha_{i}})|S_{i}|(1+\beta)^i$.

\end{itemize}
\end{document}
