%%%%%
\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{2}{October 26, 2009}{Ronitt Rubinfeld}{Svetlana Olonetsky \& Iftah Gamzu} %

\section{Lecture Outline}
\begin{itemize}
  \item Chernoff bound
  \item Estimating the number of connected components
  \item Estimating the weight of the minimum spanning tree
  \item Distributed algorithms vs.\ sublinear time algorithms
\end{itemize}

\section{Chernoff Bound} \label{sec:bound}
Let $X_1,X_2,\ldots,X_m$ be $m$ independent identically
distributed random variables such that $X_i \in [0,1]$. Let $S =
\sum_{i=1}^{m} X_i$ and $p = \mathrm{E}[X_i] = \mathrm{E}[S]/m$.
Then,
$$
\Pr \left( \abs{\frac s m - p} \geq \delta p \right) \leq
e^{-\Omega\big( m p \delta^2\big)} \ .
$$

\section{Estimating the Number of Connected Components}

Given an undirected graph $G(V,E)$ having $n$ nodes and maximal
degree $d$ (in an adjacency list representation), and $\epsilon$,
we want to find an $\epsilon n$-additive estimate of the number of
connected components. Specifically, if $c$ denotes the number of
connected components in $G$ then the estimated number of connected
components $y$ should satisfy
$$
c-\epsilon n \leq y \leq c+\epsilon n
$$

\begin{definition}
Let $n_u$ be the number of nodes in $u$'s connected component.
\end{definition}

\begin{observation}
For any connected component $A \subseteq V$, we have
$$
\sum_{u \in A} \frac{1}{n_u} = \sum_{u \in A} \frac{1}{|A|} = 1 \
.
$$
Furthermore, this implies that the number of connected components
$c$ is equal to
$$
c = \sum_{u \in V} \frac{1}{n_u} \ .
$$
\end{observation}

\begin{definition}
Let $\hat{n}_u = \min\{ n_u, 2 / \epsilon \}$, and let $\hat{c} =
\sum_{u \in V} 1 / \hat{n}_u$.
\end{definition}

The following lemma bounds the amount by which the estimates can
be off.

\begin{lemma} \label{lemma_n_u}
For any node $u$, it holds that
$$
\abs {\frac 1 {\hat{n}_u} - \frac 1 {n_u} } \leq \frac{\epsilon}
2\ .
$$
\end{lemma}
\begin{proof}
We know that $\hat{n}_u \leq n_u$ by the definition of
$\hat{n}_u$. If $n_u \leq {2} / {\epsilon}$ then $\hat{n}_u =
n_u$, and therefore, the left hand side in the above inequality is
equal to $0$. If $n_u
> {2} / {\epsilon}$ then ${\epsilon} / {2} = {1}/ {\hat{n}_u} \geq
{1}/ {n_u} \geq 0$ and the lemma follows.
\end{proof}
\begin{corollary} \label{cor:n_u}
$\abs{ c - \hat{c} } \leq {\epsilon n} / 2$.
\end{corollary}

\begin{lemma}
We can compute $\hat{n}_u$ in $O(d / \epsilon)$ time.
\end{lemma}
\begin{proof}
We begin by presenting the algorithm that computes $\hat{n}_u$.
\begin{tabbing}
\qquad\=\qquad\=\kill
\textsf{estimate\_cc}($u$)\\
\> \textbf{run} BFS from $u$ until: \\
\> \> $\bullet$ visited the whole connected component \\
\> \> $\bullet$ or visited $2 / \epsilon$ distinct nodes of the connected component\\
\> \textbf{output} the number of visited nodes
\end{tabbing}
It is clear that during execution of the algorithm at most $2 /
\epsilon$ nodes are visited. Since the degree of each node is at
most $d$, the running time of the algorithm is $O(d / \epsilon)$.
\end{proof}

We now present algorithm \textsf{approx\_num\_cc}($G, \epsilon$),
which calculates an $\epsilon n$-additive estimation of the number
of connected components.
\begin{tabbing}
\qquad\=\qquad\=\kill
\textsf{approx\_num\_cc($G, \epsilon$)}:\\
\> \textbf{choose} a set $U = \{u_1,u_2,\ldots,u_r\}$ of $r = \Theta(1/ \epsilon^3)$ random nodes\\
\> \FOR $\,$ each $u \in U$ compute $\hat{n}_{u}$ using \textsf{estimate\_cc}($u$)\\
\> \textbf{output} $\tilde{c} = \frac n r \sum_{u \in U} \frac 1
{\hat{n}_u}$
\end{tabbing}

One can easily verify that the running time of the algorithm is
$O(1/ \epsilon^3 \cdot d/\epsilon) = O(d / \epsilon^4)$. We turn
to prove that $\tilde{c}$ is an $\epsilon n$-additive estimation
of $c$ with constant probability.

\begin{theorem} $\Pr (\abs{\tilde{c}-\hat{c}} \leq \epsilon n / 2) \geq
3/4$.
\end{theorem}
\begin{proof}
We apply the Chernoff bound from Section~\ref{sec:bound} with $p =
\mathrm{E}[1 / \hat{n}_{u_i}]$, $S = \sum_{i = 1}^{r} 1 /
\hat{n}_{u_i}$, $m = r$, and $\delta = \epsilon / 2$, and get that
$$
\Pr \left( \abs{\frac{1}{r} \sum_{i = 1}^{r}
\frac{1}{\hat{n}_{u_i}} - \mathrm{E} \left [\frac{1}{\hat{n}_{u_i}
} \right ] } \geq \frac{\epsilon}{2} \mathrm{E} \left
[\frac{1}{\hat{n}_{u_i}} \right ] \right ) \leq \exp \left
({-\Omega \left (r \mathrm{E} \left [\frac{1}{\hat{n}_{u_i}}\right
] \left (\frac{\epsilon}{2}\right)^2\right )}\right ) \ .
$$
Notice that $\tilde{c} = n / r \cdot \sum_{i = 1}^{r} 1 /
\hat{n}_{u_i}$, $\mathrm{E}[1/ \hat{n}_{u_i}] = 1/n \cdot \sum_{i
= 1}^{n} 1/ \hat{n}_{u_i} = \hat{c} / n $, and $r = \Theta(1/
\epsilon^3)$, and thus,
$$
\Pr \left ( \abs{ \frac{\tilde{c}} n - \frac{\hat{c}} n} \geq
\frac{\epsilon} 2 \frac {\hat{c}} n \right) = \Pr \left ( \abs{
\tilde{c} - \hat{c}} \geq \frac{\epsilon} 2 \hat{c} \right) \leq
\exp \left ({-\Omega \left (r \frac{\hat{c}} {n} \left
(\frac{\epsilon}{2}\right)^2\right )}\right ) = \exp \left
({-\Omega\left(\frac 1 {\epsilon} \frac {\hat{c}} n\right)}\right)
$$
By the definition of $\hat{n}_u$, we know that $\epsilon / 2 \leq
1/\hat{n}_u \leq 1$, and therefore, $\epsilon n / 2 \leq \hat{c}
\leq n $. Consequently, we attain that
$$
\Pr \left ( \abs{ \tilde{c} - \hat{c}} \geq \frac{\epsilon} 2 n
\right) \leq \Pr \left ( \abs{ \tilde{c} - \hat{c}} \geq
\frac{\epsilon} 2 \hat{c}\right) \leq e^{-\Omega(1)} < \frac 1 4 \
.
$$
\end{proof}
\begin{corollary} $\Pr( \abs{c-\tilde{c}}
\leq {\epsilon}n) \geq 3/4$.
\end{corollary}
\begin{proof}
By Corollary~\ref{cor:n_u} and the triangle inequality
$\abs{c-\tilde{c}} \leq \abs{c-\hat{c}} +
\abs{\hat{c}-\tilde{c}}$, one can obtain that $\Pr(
\abs{c-\tilde{c}} \leq {\epsilon}n) = \Pr (\abs{\tilde{c}-\hat{c}}
\leq \epsilon n / 2)$.
\end{proof}

\section{Estimating the Weight of the Minimum Spanning Tree}

\subsection{Problem statement}

The input for the problem is a connected undirected graph $G = (V,
E)$ in which the degree of each node is at most $d$. Furthermore,
each edge $(i,j)$ has an integer weight $w_{ij} \in [w] \cup
\{\infty\}$. Note that the graph is given in an adjacency list
format, and edges of weight $\infty$ do not appear in it. The goal
is to find the weight of a minimum spanning tree (MST) of $G$.
Specifically, if we let $w(T) = \sum_{(ij) \in T} w_{ij}$ for $T
\subseteq E$, then our objective is to find
$$
M = \min_{T \text{ spans } G} w(T) \ .
$$

Since we are interested in sublinear time algorithms for this
problem, and therefore, cannot hope to find $M$, we focus on
finding an $\epsilon$-multiplicative estimate of $M$, that is, a
weight $\hat{M}$ which satisfies
$$
(1-\epsilon)M \leq \hat{M} \leq (1+\epsilon)M \ .
$$

We note that $n - 1 \leq M \leq w \cdot (n - 1)$, where $n = |V|$.
This follows since $G$ is connected, and thus, any spanning tree
of it consists of $n - 1$ edges, and by the assumption on the
input weights.

\subsection{From motivation to characterization}
In what follows, we relate the weight of a MST of $G$ to the
number of connected components in certain subgraphs of $G$. We
begin by introducing the following notation for a graph $G$:

\begin{itemize}
\item Let $G^{(i)} = (V, E^{(i)})$ be the subgraph of $G$ that
consists of the edges having a weight of at most $i$.

\item Let $C^{(i)}$ be the number of connected components in
$G^{(i)}$.
\end{itemize}

\begin{figure}[!hbt]
\centerline{ \scalebox{0.40}{ \input{mst1.pstex_t} } } \caption{A
graph $G$ having $w = 2$, and its induced subgraph $G^{(1)}$.}
\label{fig:mst1}
\end{figure}

\smallskip \noindent {\bf A motivation.}
Let us consider two simple cases. The first case is when $w=1$,
namely, all the edges of $G$ have a weight of $1$. In this case,
it is clear that the weight of a MST is $n-1$. Now, let us
consider the case that $w=2$, and let us focus on $G^{(1)}$.
Clearly, one has to use $C^{(1)} - 1$ edges (of weight $2$) to
connect the connected components in $G^{(1)}$. This implies that
the weight of a MST in this case is
$$
2 \cdot (C^{(1)} - 1) + 1 \cdot (n - 1 - (C^{(1)} - 1)) = n - 2 +
C^{(1)} \ .
$$

\smallskip \noindent {\bf The characterization.}
We extend and formalize the intuition presented above.
Specifically, we characterize the weight of a MST of $G$ using the
$C^{(i)}$'s, for any integer $w$.

\begin{claim}
$M = n - w + \sum_{i = 1}^{w-1} C^{(i)}$
\end{claim}
\begin{proof}
Let $\alpha_i$ be the number of edges of weight $i$ in any MST of
$G$. Remark that it is well-known that all minimum spanning trees
of $G$ have the same number of edges of weight $i$, and hence, the
$\alpha_i$'s are well defined. It is easy to validate that the
number of edges having weight greater than $\ell$ is equal to the
number of connected components in $G^{(\ell)}$ minus 1. That is,
$\sum_{i = \ell + 1}^w \alpha_i = C^{(\ell)} - 1$, where $C^{(0)}$
is set to be $n$. Now, notice that
\begin{eqnarray*}
M & = & \sum_{i=1}^w i \cdot \alpha_i \\
  & = & \sum_{i=1}^w \alpha_i + \sum_{i=2}^w \alpha_i + \sum_{i=3}^w \alpha_i +\dots + \alpha_w \\
  & = & (n-1) + (C^{(1)}-1) + (C^{(2)}-1) + \dots + (C^{(w-1)} - 1) \\
  & = & n-w + \sum_{i=1}^{w-1} C^{(i)} \\
\end{eqnarray*}~
\end{proof}

\subsection{Approximation algorithm}

Algorithm \textsf{MST\_approx}, formally defined below, estimates
the weight of the MST.

\begin{tabbing}
\qquad\=\qquad\=\kill
\textsf{MST\_approx}($G, \epsilon, w$)\\
\> \FOR $\; i = 1$ to $w-1$ \\
\> \> $\hat{C}^{(i)} = \textsf{approx\_num\_cc}$($G^{(i)}, \epsilon / (2w)$) \\
\> \textbf{output} $\hat{M} = n - w + \sum_{i=1}^{w-1} C^{(i)}$
\end{tabbing}

\noindent {\bf Running time.} One can easily see that there are
$w$ calls to \textsf{approx\_num\_cc}. Recall that the running
time of this procedure is $O(d / (\epsilon / (2w))^4) = O(dw^4 /
\epsilon^4)$, and hence, the running time of \textsf{MST\_approx}
is $O(dw^5 / \epsilon^4)$. It is worth noting that rather than
extracting $G^{(i)}$ from $G$ for each call of
\textsf{approx\_num\_cc} (which would make the algorithm have
non-sublinear time), we simply modify \textsf{approx\_num\_cc} so
it ignores edges with weight greater than $i$.

\smallskip \noindent {\bf Approximation guarantee.}
We establish that $(1 - \epsilon) M \leq \hat{M} \leq (1 +
\epsilon) M$ with high probability (whp). For this purpose, recall
that \textsf{approx\_num\_cc} outputs an estimation
$\hat{C}^{(i)}$ of the number of connected components which
satisfies $|\hat{C}^{(i)} - C^{(i)}| \leq n\epsilon/ (2w)$ whp.
Consequently, we get that $|M - \hat{M}| \leq n\epsilon / 2$ whp.
Notice that $M \geq n-1 \geq n/2$, where the last inequality is
valid for any ``interesting'' $n$, i.e., $n \geq 2$. Therefore,
$|M - \hat{M}| \leq M\epsilon$, which completes the proof.

\smallskip \noindent {\bf Concluding remark.}
The current state of the art algorithm for finding an
$\epsilon$-multiplicative estimate of $M$ has a running time of
$O(dw / \epsilon^2 \cdot \log dw / \epsilon)$. On the lower bound
side, it is known that the running time of any algorithm must be
$\Omega(dw / \epsilon^2)$.

\section{Distributed Algorithms vs.\ Sublinear Time Algorithms}

We introduce a definition and a theorem, which will be used in the
next lesson.

\begin{definition}
$\hat{y}$ is an \emph{($\alpha,\epsilon$)-estimate} of a solution
value $y$ for a minimization problem of size $n$ if $$y \leq
\hat{y} \leq \alpha y + \epsilon n \ .$$
\end{definition}

\begin{theorem}\emph{(Vizing's Theorem)}
Every graph is edge-colorable\footnote{An \emph{edge coloring} of
a graph is an assignment of colors to the edges of the graph so
that no two adjacent edges have the same color.} with at most
$d+1$ colors, where $d$ is the maximum degree of the graph.
\end{theorem}
\begin{corollary}
Every graph whose maximum degree is $d$ has a matching of size at
least $|E| / (d+1)$.
\end{corollary}
\begin{corollary}
The vertex cover size of every graph whose maximum degree is $d$
is at least $|E| / (d+1)$.
\end{corollary}

\end{document}
