\documentclass[10pt]{article}
\newtheorem{define}{Definition}
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{automata,positioning}
\usetikzlibrary{decorations.pathmorphing,shapes}
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}
\lecture{4}{February 19, 2019}{Ronitt Rubinfeld}{Allison Tam}

\section{Overview}
\begin{itemize}
  \item Distributed algorithms overview
  \item Parnas-Ron Framework
  \item Vertex cover approximations (sublinear and distributed)
\end{itemize}
Today, we covered how to use distributed local algorithms to inspire sublinear time sequential algorithms. The overall idea is to use the insights and understandings leveraged in distributed algorithms. Historically, this has led to a blending of ideas in the two fields. In lecture, we focus on a sublinear approximation algorithm of a vertex cover.

\section{Distributed Algorithms}
\subsection{Overview}
The input to a distributed algorithms problem is a network, consisisting of processors (nodes) connected by links (edges). Unlike in parallel algorithms, computation is performed by the communication network \textbf{on} the communication network. In other words, the input graph is the network itself. For the purpose of this class, we assume the following properties of the network.
\begin{enumerate}
  \item max degree $d$
  \item each processor knows its neighbors
  \item synchronous computation -- processors reliably send messages to each other during synchronized rounds of communication
\end{enumerate}
Each round operates in the following fashion.
\begin{enumerate}
  \item Nodes perform computation on their input bits, random bits, and history of communication.
  \item Nodes send messages to neighbors. Messages don't necessarily have to be the same.
  \item Nodes receive messages.
\end{enumerate}

\subsection{Connection to Sublinear Time}
In the above setup, we can simulate the output of the distributed algorithm. Suppose we are interested in node $v$'s state. After one round, $v$'s output is based on its information and its immediate neighbors'. After two rounds, $v$ implicitly learns information from its neighbors' neighbors. Using induction, after $k$ rounds of an algorithm, node $v$ knows and uses information from nodes at most $k$ links away.

This implies that you can know $v$'s output using a sequential simulation that uses $O(d^k)$ queries. The simulation only requires us to look at nodes within a $k$-radius ball of $v$, because information from elsewhere in the graph won't otherwise play a role in $v$'s output. There are lots of useful $k$-round distributed algorithms for $k$ constant or $\log\log n$.

In sublinear time algorithms, we often sample and test for some property. We can abstract the fast distributed algorithm as an oracle that simply tells us if a node has some property.

\section{Vertex Cover}
Given $G=(V,E)$, $V'\subseteq V$ is a \textbf{vertex cover} if $\forall (u,v)\in E$, either $u$ or $v \in V'$. From 6.046, we know that finding the minimum vertex cover size is NP-hard. We also know that we can find a 2-approximation of vertex cover size in polynomial time.

Assume that we have a bounded degree $d$ graph, where $d\geq 2$ and is a constant. Without this, the problem becomes much harder.

Let $\abs{V'}$ be the size of the vertex cover of $G$. For a connected, bounded graph, we can conclude that $\abs{V'} \geq \frac{m}{d} \geq \frac{n}{d}$. This can be shown through contradiction. Each vertex in $V'$ can cover at most $d$ edges, which in total must exceed $m$.

\subsection{Distributed Subroutine}
Now, we go over a distributed algorithm that returns a valid vertex cover.
\begin{algorithm}[!ht]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
  \Input{Graph $G=(V,E)$}
  \Output{Approximated vertex cover $A$}
  $i \gets 0$ \;
  \While{edges remain in $E$}
    {
    Let $U$ be the set of nodes in $V$ with degree $\geq \frac{d}{2^i}$ \;
    $A \gets A\cup U$ \;
    Remove $U$ from $V$ and incident edges from $E$ \;
    Update degrees of remaining nodes in graph \;
    $i \gets i+1$ \;
    }
  Return $A$ \;
    \caption{Distributed Algorithm for Vertex Cover}
    \label{alg:distr}
\end{algorithm}
\subsubsection*{Example Walkthrough}
\begin{figure}[!htbp]
\centering
\begin{tikzpicture}[font=\sffamily]
        % Setup the style for the states
        \tikzset{unfill/.style={state,
                                    minimum size=0.5cm,
                                    line width=0.5mm,
                                    fill=gray!10!white}}
        \tikzset{round2/.style={state,
                                    minimum size=0.5cm,
                                    line width=0.5mm,
                                    fill=blue!20!white}}
        \tikzset{round3/.style={state,
                                    minimum size=0.5cm,
                                    line width=0.5mm,
                                    fill=green!10!white}}
        \tikzset{round1/.style={state,
                                    minimum size=0.5cm,
                                    line width=0.5mm,
                                    fill=orange!20!white}}

        % Draw the states
        \node[unfill] at (0, 3)         (a)     {};
        \node[unfill] at (0, 2)     (b)     {};
        \node[unfill] at (0, 1)     (c)     {};
        \node[unfill] at (4, 2)     (d)     {};

        \node[round2] at (2, 2)     (2a)     {};
        \node[round2] at (-2, 2)     (2b)     {};

        \node[round3] at (-0.5, 4)     (3a)     {};
        \node[round3] at (-2, 3)     (3b)     {};

        \node[round1] at (-4, 2)     (1a)     {};
        \node[round1] at (1.5, 4)     (1b)     {};

        \draw[thick, line width=0.5mm,] (a) -- (2a);
        \draw[thick, line width=0.5mm,] (a) -- (2b);
        \draw[thick, line width=0.5mm,] (b) -- (2a);
        \draw[thick, line width=0.5mm,] (b) -- (2b);
        \draw[thick, line width=0.5mm,] (c) -- (2a);
        \draw[thick, line width=0.5mm,] (c) -- (2b);
        \draw[thick, line width=0.5mm,] (d) -- (2a);
        \draw[thick, line width=0.5mm,] (2b) -- (3b);
        \draw[thick, line width=0.5mm,] (3b) -- (3a);
        \draw[thick, line width=0.5mm,] (3a) -- (1b);
        \draw[thick, line width=0.5mm,] (2b) -- (1a);
        \draw[thick, line width=0.5mm,] (2b) -- (1a);

        \draw[thick, line width=0.5mm,] (1a) -- (-5, 3);
        \path (-5, 1) -- node[auto=false]{\Huge \vdots} (-5, 3);
        \draw[thick, line width=0.5mm,] (1a) -- (-5, 1);

        \draw[thick, line width=0.5mm,] (1b) -- (2.5, 3);
        \path (2.5, 3) -- node[auto=false]{\Huge \vdots} (2.5, 5);
        \draw[thick, line width=0.5mm,] (1b) -- (2.5, 5);
    \end{tikzpicture}
    \caption{\label{fig:ex} Consider a graph with bounded degree 8. Orange nodes have degree 8.}
\end{figure}
In round 0, the orange nodes are added to $A$, because they have degree $\geq 8$. In round 1, the blue nodes, with degree 4, are added to $A$. In round 2, no modifications are made. In round 3, the green nodes, now only connected to one another, are both added to $A$.

After the algorithm terminates at $\log_2 d = 4$ rounds, each node will know if it is in $A$.
\begin{claim}
$A$ is a valid vertex cover.
\end{claim}
\begin{proof}
At the end of algorithm \ref{alg:distr}, no edges remain. All removed edges must have at least one node added to $A$.
\end{proof}
\begin{theorem}
Let $\theta$ be any vertex cover of graph $G$. Algorithm \ref{alg:distr} will output a valid vertex cover $A$, such that $\abs{\theta} \leq \abs{A} \leq (1+2\log d)\abs{\theta}$.
\end{theorem}
\begin{proof}
Each round in algorithm \ref{alg:distr} adds at most $2\abs{\theta}$ nodes that are not in $\theta$ to $A$. Let $X$ be the set of nodes that are removed during round $i$ and are not in $\theta$. Observe that for all nodes in $X$, every one of their neighbors must be in $\theta$, since $\theta$ is a vertex cover and $X$ has no overlap with $\theta$.

Let $\abs{E_X}$ be the edges incident to $X$. On the $i$th iteration, all newly removed nodes have degree $\geq \frac{d}{2^i}$, so $\abs{E_X} \geq \abs{X} \frac{d}{2^i}$. Furthermore, because previous iterations removed high degree nodes, {\em all} remaining nodes have degree $\leq \frac{d}{2^{i-1}}$. That combined with the above observation (all $E_X$ end in $\theta$) implies that $\abs{E_X}$ has an upper bound of $\abs{\theta} \frac{d}{2^{i-1}}$ when all edges are connected to vertices not yet removed.
$$\abs{X} \frac{d}{2^i}\leq \abs{E_X} \leq \abs{\theta} \frac{d}{2^{i-1}}$$
$$\abs{X}\leq 2\abs{\theta}$$
If each round adds at most $2\abs{\theta}$ nodes not in $\theta$, then at most $2\log d$ additional nodes can be added to $A$, and the theorem follows directly.
\end{proof}

The distributed algorithm achieves an $O(\log d)$ approximation in simulated $O(d^{\log d})$ queries.
\subsection{Using Parnas-Ron Framework}
The \textbf{Parnas-Ron framework} samples nodes, simulates the distributed algorithm to check if a node is in the vertex cover, and extrapolates and estimate from the results. We pick $r$ based on desired $\epsilon$. Using Chernoff, we require $r=O(\frac{1}{\epsilon^2})$.
\begin{algorithm}[!ht]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
  \Input{Graph $G$, $\epsilon$}
  \Output{$\hat v$}
  $i \gets 0$ \;
  $r \gets \frac{1}{\epsilon^2}$ \;
  Sample $r$ vertices $v_1, \cdots, v_r$ from $G$ uniformly with replacement \;
  \For{$k=1$ to $r$}
    {Simulate algorithm \ref{alg:distr} to see if $v_k$ is in the vertex cover\;
    \If{$v_k$ in vertex cover} {$i \gets i + 1$ \;}
    }
  Return $\hat v = (\frac{i}{r})n$ \;
    \caption{Sublinear Vertex Cover (Parnas-Ron Framework)}
    \label{alg:prf}
\end{algorithm}

Overall runtime is $O(rd^{\log d}) = O(\frac{1}{\epsilon^2}d^{\log d})$, which doesn't depend on $n$. Additive error comes from using sampling. Multiplicative error comes from the fact that the subroutine is an approximation.

\begin{definition}
$\hat y$ is a $(\alpha, \epsilon)$-approximation of true value $y$ for a minimization problem if $y\leq \hat y\leq \alpha y + \epsilon n$.
\end{definition}

Algorithm \ref{alg:prf} gives an $(O(\log d, \epsilon n))$-approximation in $d^{O(\log d)}$ queries. As food for thought, another algorithm uses the Parnas-Ron framework to achieve a $(2,\epsilon n)$-approximation in $d^{O(\frac{1}{\epsilon}\log d)}$ queries.
\end{document}
