%% LyX 1.6.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[10pt,english]{article}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{graphicx}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\theoremstyle{plain}
\theoremstyle{plain}
\newtheorem{thm}{Theorem}
  \theoremstyle{definition}
  \newtheorem{defn}[thm]{Definition}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newtheorem{define}{Definition}%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}
\oddsidemargin=0.15in\evensidemargin=0.15in\topmargin=-.5in\textheight=9in\textwidth=6.25in

\usepackage{babel}

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

\lecture{3}{November 2, 2009}{Ronitt Rubinfeld}{Margarita Vald
$\&$ Anat Ganor}


\section*{Introduction}

In this lecture we explore the connection between local distributed
algorithms and sublinear time algorithms on sparse graphs. We will
see how a round-efficient distributed algorithm may be used to construct
a sublinear time algorithm.

Similar methods work for a range of problems that can be referred
to as positive linear programming (LP) problems and deal with covering
and packing questions (such as vertex cover, matching and dominating
set). These problems, when working on sparse graphs, have local distributed
algorithms (that use only few rounds).

This lecture will focus on an algorithm for approximating the vertex
cover problem.
\begin{defn}
[Vertex cover]\textit{Given $G=(V,E)$, $V'\subset V$ is a vertex
cover if $\forall e=\left(u,v\right)\in E$ either $u\in V'$ or $v\in V'$.
}
\end{defn}

\subsection*{Approximating Minimum Vertex Cover using Linear Programing}
\begin{defn}
[Integer Programming] \textit{Given an objective function, and
a collection of linear constraints, find an assignment of 0-1 values
to the variables such that all linear constraints are satisfied and
the objective function is optimized. }
\end{defn}

\subsubsection*{Vertex Cover as Integer Constraints:}

For a graph $G=(V,E)$ , we have variables $X_{i}$, which will be
either $0$ or $1$, indicating whether vertex $i$ is part of the
cover.\begin{eqnarray*}
Minimize & \sum_{i=1}^{n}X_{i}\\
subject\; to & X_{i}+X_{j}\geq1 & for\; each\;\left(i,j\right)\in E\\
 & X_{i}\in\left\{ 0,1\right\}  & for\; each\; i\in V\end{eqnarray*}


Integer programming is NP-complete and therefore we will consider
the linear programming relaxation:

\begin{eqnarray*}
Minimize & \sum_{i=1}^{n}X_{i}\\
subject\; to & X_{i}+X_{j}\geq1 & for\; each\;\left(i,j\right)\in E\\
 & X_{i}\in\left[0,1\right] & for\; each\; i\in V\end{eqnarray*}


\emph{\underline{The LP Rounding Algorithm \\}}
\begin{itemize}
\item Solve LP relaxation optimally to get fractional solution $x^{*}$
\item Round the fraction values to obtain a solution to the vertex cover
problem, i.e., $S=\left\{ i|\; x_{i}^{*}\geq\frac{1}{2}\right\} $ 
\item Return $S$ \\

\end{itemize}
\begin{claim} \textit{The set $S$ obtained by rounding the LP-relaxation
is a vertex cover.}\end{claim} 

\begin{claim}\textit{The vertex cover $S$ returned by the LP rounding
is at most 2-times the optimal cover.}\end{claim}

We will work on sparse graphs and assume that $d$ is the maximum
degree and that the average degree $\overline{d}$ is $\Omega(d)$.
Since on such graphs the cover is large (approximately $\frac{n}{2}$
vertices), every vertex that is chosen at random is likely to be in
the cover. 
\begin{defn}
\textit{$y'$ is $(\alpha,\epsilon)$-estimate of $y$ if $y\leq y'\leq\alpha y+\epsilon\cdot n$
(for $\alpha>1$ and $\epsilon<1$)}
\end{defn}
We will see a sublinear time algorithm that computes an $(2\log d+1,\epsilon)$
approximation for vertex cover. Note that this approximation isn't
very good when $\overline{d}$ is large.


\subsubsection*{Our assumptions}

We will assume the following: 
\begin{itemize}
\item Our input graph will be a communication network, where every node
is a processor and every edge is a line of communication (see Figure
\ref{fig:communication-network})
\item The network is synchronous. In each round, each processor talks to
each of its neighbors 
\item The graph is sparse with maximum degree $d$ and average degree $\overline{d}=\Omega(d)$ 
\item Every processor knows $d$ 
\item After $k$ rounds each processor decides if it's in the cover or not 
\end{itemize}
%
\begin{figure}
\begin{center}\includegraphics[scale=0.36]{Com_Net}\end{center}\caption{\label{fig:communication-network}Communication network graph}

\end{figure}



\section*{Simple Case}

First we will assume that there's a deterministic distributed algorithm
$\mathcal{D}$ that can solve the vertex cover problem in only $k$
rounds. We will see a sublinear \textquotedbl{}Oracle Reduction Algorithm\textquotedbl{}
that estimates the cover size based on this assumption. \\
 The new algorithm is a reduction from $\mathcal{D}$. It uses
an oracle which computes the output of $\mathcal{D}$ and for every
query on a vertex $v$ tells if $v$ is in the cover or not. Since
the oracle can answer using $k$ rounds, the answer can be affected
only by the vertices and edges that can be reached from $v$ during
$k$ steps. We will call this sub graph the \textquotedbl{}\textbf{$\mathbf{\mathit{\mathbf{k}}}$
neighborhood}\textquotedbl{} of $v$.

\begin{theorem}\textit{ Given a deterministic distributed algorithm
$\mathcal{D}$ that in $k$ rounds computes exactly a vertex cover
$\mathcal{C}$, there's a sublinear algorithm with query complexity
$O(\frac{d^{k+1}}{\epsilon^{2}})$ that computes $c$ s.t. $|\mathcal{C}|\leq c\leq|\mathcal{C}|+\epsilon n$.
}\end{theorem}

\begin{proof2} \\


\emph{\underline{The Oracle Reduction Algorithm (with oracle access to $\mathcal{D}$)\\}} 
\begin{itemize}
\item \emph{Generating $S$}: pick $s=\frac{8}{\epsilon^{2}}$ nodes i.i.d
from $[n]$ 
\item $\forall v\in S$, let $G_{k}(v)$ be the \textquotedbl{}$k$ neighborhood\textquotedbl{}
of $v$ 

\begin{itemize}
\item query $\mathcal{D}(G_{k}(v))$ 
\item Define $X_{v}=\begin{cases}
1 & \mbox{if \ensuremath{\mathcal{D}(G_{k}(v))\:}adds \ensuremath{v\:}to cover}\\
0 & o.w.\end{cases}$
\end{itemize}
\item Output $c=n\cdot\left(\frac{1}{s}\cdot\sum_{v\in S}X_{v}\right)+\frac{\epsilon n}{2}$ 
\end{itemize}

\paragraph*{Correctness\protect \\
}

The $X_{v}$'s cover is identical to $\mathcal{C}=\mathcal{D}(G)$,
i.e., $X_{v}=1$ iff $v\in\mathcal{C}$. Also, we have $E[X_{v}]=\frac{1}{n}\cdot\sum_{v\in V}X_{v}$
which can be approximated using $\frac{1}{s}\cdot\sum_{v\in S}X_{v}$
\\
This way we can estimate $|\mathcal{C}|=n\cdot E[X_{v}]$ \\
By the additive Chernoff bound we have:\[
Pr\left[\left|\frac{1}{s}\cdot\underset{v\in S}{\sum}X_{v}-E\left[X_{v}\right]\right|\geq\frac{\epsilon}{2}\right]\leq\frac{1}{3}\]



\paragraph*{Query complexity\protect \\
}

The query complexity of the algorithm is $O(\frac{d^{k+1}}{\epsilon^{2}})$
where $\frac{1}{\epsilon^{2}}$ is the number of times we look at
$G_{k}(v)$ for some $v$ in $S$ and $d^{k+1}$ is an upper bound
on the number of vertices in $G_{k}(v)$. \\
Note that every call to the oracle is considered one step of computation
and we ignore the size of the messages. \end{proof2}

\begin{remark} 
\begin{itemize}
\item Adding $\frac{\epsilon n}{2}$ is just a shift to get $|\mathcal{C}|\leq c\leq|\mathcal{C}|+\epsilon n$
instead of $|\mathcal{C}|-\frac{\epsilon n}{2}\leq c\leq|\mathcal{C}|+\frac{\epsilon n}{2}$ 
\item To reduce the error range we can run the same algorithm many times
and return the median (see homework 0, question 2) 
\end{itemize}
\end{remark}


\section*{General Case}

The algorithm we used in the simple case to solve vertex cover in
polytime doesn't exist. Therefore, we will use a randomized distributed
algorithm $\mathcal{D}$ which gives an approximation. Although $\mathcal{D}$
is randomized and returns an approximation, the \textquotedbl{}Oracle
Reduction Algorithm\textquotedbl{} can work the same way as before.
To do that, we have to make sure all of $\mathcal{D}$ answers are
consistent, so we must ensure that each processor $w$ uses the $\emph{same}$
random bits in every computation of $\mathcal{D}((G_{k}(v))$ for
which $w$ is in the $k$ neighborhood of $v$. 


\subsection*{A Distributed Approximation Algorithm for Vertex Cover}

The following is a distributed randomized algorithm. On every step
it adds to the cover a vertex chosen at random out of the remaining
vertices. We will show that this algorithm gives a multiplicative
approximation and use it as the oracle of the \textquotedbl{}Oracle
Reduction Algorithm\textquotedbl{}. 

\ 

\emph{\underline{Distributed Approximation Algorithm for Vertex Cover (assume maximum degree d)\\}} 
\begin{itemize}
\item $\mathcal{C}\leftarrow\emptyset$ 
\item For $i=1$ to $\log d$ do: 

\begin{itemize}
\item Each vertex $v$ with degree $\geq\frac{d}{2^{i}}$ adds itself to
$\mathcal{C}$ 
\item For all added $v$ remove $v$ and all adjacent edges from $V$ 
\item Update degrees of all remaining vertices 
\end{itemize}
\item Output $|\mathcal{C}|$ 
\end{itemize}
\begin{theorem}\textit{ Let $VC_{G}$ be the optimal solution for
the vertex cover problem. The algorithm above gives a multiplicative
approximation of $(2\log d+1)$, i.e. $VC_{G}\leq|\mathcal{C}|\leq(2\log d+1)VC_{G}$}
\end{theorem}

\begin{proof2}Let $G=\left(V,E\right)$ be a graph with maximum degree
$d$.
\begin{description}
\item [{LHS:}] Since at the end of run no edges remain and edge is removed
only when one of its nodes is inserted into $\mathcal{C}$ $\Longrightarrow\mathcal{C}$
is a vertex cover
\item [{RHS:}] Let $\theta$ be a minimum vertex cover. therefore, $\left|\theta\right|=VC_{G}$
and $\bar{\theta}=V\setminus\theta$ \begin{claim}\textit{ In each
iteration, the number of new vertices from $\bar{\theta}$ that added
to $\mathcal{C}$ is $\leq2\cdot VC_{G}$}\end{claim}\begin{proof2}Let
$Y_{i}$ be the vertices considered in iteration $i$. (i.e., current
degree between $\frac{d}{2^{i-1}}$ and $\frac{d}{2^{i}})$. Let $X_{i}=Y_{i}\cap\bar{\theta}$.
%
\begin{figure}[h]
\begin{center}\includegraphics[scale=0.53]{Partition}\end{center}\caption{\label{fig:The-partition-of}The partition of the vertices in the
$i$th iteration}

\end{figure}
\\
Note that\textbf{ }all edges from $X_{i}$ must go to $\theta$
since $\theta$ is a vertex cover (see Figure \ref{fig:The-partition-of}).
Therefore, $\left|X_{i}\right|\cdot\frac{d}{2^{i}}\leq\left|\theta\right|\frac{d}{2^{i-1}}$,
which implies that $\left|X_{i}\right|\leq2\cdot\left|\theta\right|\leq2\cdot VC_{G}$
\end{proof2}\\
By the claim we obtain that $\left|\mathcal{C}\right|\leq\left(2\log d+1\right)VC_{G}$. 
\end{description}
\end{proof2}

\begin{corollary} \textit{Using the algorithm above as the oracle
of the \textquotedbl{}Oracle Reduction Algorithm\textquotedbl{} yields
a $(2\log d+1,\epsilon)$ approximation for vertex cover using $\frac{d^{O(\log d)}}{\epsilon^{2}}$
queries }\end{corollary}


\section*{Maximal Matching}
\begin{defn}
[Matching]\textit{Given a graph $G=(V,E)$, a \emph{matching} $M$
in $G$ is a set of pairwise non-adjacent edges; that is, no two edges
share a common vertex.}
\end{defn}
~
\begin{defn}
[Maximal matching]\textit{A \emph{maximal matching} is a matching
$M$ of a graph $G$ with the property that if any edge not in $M$
is added to $M$, it is no longer a matching.}
\end{defn}
~
\begin{defn}
[Maximum matching] \textit{A \emph{maximum matching} is a matching
that contains the largest possible number of edges. There may be many
maximum matchings. }
\end{defn}
Figure \ref{fig:maximum-matching-vs.} depicts examples of maximum
matching and maximal matching.\\


%
\begin{figure}
\begin{center}\includegraphics[scale=0.48]{Matching}\end{center}\caption{\label{fig:maximum-matching-vs.}(a) Maximum matching (b) Maximal
matching}

\end{figure}


\begin{remark} 
\begin{itemize}
\item Every maximum matching is maximal, but not every maximal matching
is a maximum matching. 
\item The size of maximal matching is at most the size of the vertex cover.
\item In graphs where $deg\leq d$ the size of maximal matching$\geq\frac{m}{2d-1}$.\\
Proof: Each edge $e$ that is in the matching, exclude at most
$2d-2$ other distinct edges (besides $e$ itself). Therefore, the
number of edges in the matching is $\geq\frac{m}{2d-1}$.
\end{itemize}
\end{remark} 

\emph{\underline{Greedy Sequential Maximal Matching Algorithm}}\\

\begin{itemize}
\item $M\leftarrow\emptyset$
\item $\forall e=\left(u,v\right)\in E$

\begin{itemize}
\item if neither $u$ nor $v$ matched, add $e$ to $M$
\end{itemize}
\item Output $M$
\end{itemize}
\begin{claim}\textit{ $M$ is a maximal matching}\end{claim}

\begin{proof2}Let $e=\left(u,v\right)\in E$ s.t $e\notin M$, then
$u$ or $v$ matched. \end{proof2}


\subsection*{Implementing Oracle to Simulate Greedy}

We would like to implement an oracle by simulating the above greedy
algorithm.

To decide if an edge $e$ is in the matching :
\begin{itemize}
\item We must know if adjacent edges that come before $e$ in the ordering
of edges are in the matching --- if any are in the matching, $e$
is not; and only if all are not in the matching, the algorithm puts
$e$ in the matching. 
\item Note that we do not need to know anything about edges that come after
$e$ in the ordering. 
\item We want that the time that it takes to decide about $e$ will not
depend on $n$. 
\end{itemize}
The problem is that there might be long dependency chains (see Figure
\ref{fig:Implementing-oracle-to}). \\
 %
\begin{figure}
\begin{center}\includegraphics[clip,scale=0.6]{Oracle}\end{center}\caption{\label{fig:Implementing-oracle-to}Implementing the oracle. The query
$\left(4,5\right)\in M$ will cause a long dependency chain.}

\end{figure}
\\
In the first case only the even edges are in the matching and
in the second only the odd ones. When asked if edge $i$ is in the
matching, the algorithm must check recursively all edges $1,2,...,i$
to get the answer. This requires $\Theta\left(i\right)$ recursion
steps.\\
 \\
This can be solved by taking a random order of edges. When viewing
the edges at a random order, the dependency chains break. The expected
length of a dependency chain will not depend on $n$. \\
 %
\begin{figure}[h]
\begin{center}\includegraphics[scale=0.6]{Improved}\end{center}\caption{\label{fig:Improved-oracle-implementation}Improved oracle implementation}

\end{figure}
\\
This is demonstrated in Figure \ref{fig:Improved-oracle-implementation}:
In this example we pick a random number between 0 and 1 for every
edge to determine the order of the edges. When asked on edge $0.5$
the algorithm will have to check only the edges $0.3$ on the right
side and $0.4,0.2$ on the left side. The rest do not affect the answer.
\end{document}
