\documentclass[10pt]{article}
\newtheorem{define}{Definition}
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{automata,positioning}
\usetikzlibrary{decorations.pathmorphing,shapes}
\usepackage{enumitem}
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}
\newcommand{\D}{\Delta}
%\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}{September 10, 2020}{Ronitt Rubinfeld}{Henry Hu}

\section{Overview}

Today, we covered the following topics:

\begin{itemize}
  \item Vertex Cover
  \item Distributed model (Local model) 
  \item Parnas-Ron Framework for reducing sublinear to distributed approximations
  \item Sublinear algorithm for Approximate Vertex Cover (Parnas-Ron)
\end{itemize}

\section{Vertex Cover}\label{section:vertexcover}
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.

\subsection{Example cases}\label{subsection:examples}

\begin{enumerate}
    \item Graph with no edges \label{listitem:noedges}
    \begin{itemize}
        \item The size of the minimum vertex cover is $0$.
    \end{itemize}
    \item Graph with one edge \label{listitem:oneedge}
    \begin{itemize}
        \item The size of the minimum vertex cover is $1$ (by taking either of the endpoints).
    \end{itemize}
    \item Star: $|V| - 1$ vertices, each of degree $1$, connected to a central node.
    \begin{itemize}
        \item The size of the minimum vertex cover is $1$ (by taking the central node).
    \end{itemize}
    \item $k$-clique
    \begin{itemize}
        \item The size of the minimum vertex cover is $k - 1$ (by taking any less vertices we would miss an edge between the remaining vertices).
    \end{itemize}
    \item $n$-cycle
    \begin{itemize}
        \item The size of the minimum vertex cover is $\left\lceil\frac{n}{2}\right\rceil$ (by taking every other vertex).
    \end{itemize}
    \item Graph with nodes of degree $\leq \D$, where $\D\geq 2$ is a constant
    \begin{itemize}
        \item The size of the minimum vertex cover is $\geq \frac{\abs{E}}{\D} \geq \frac{\abs{V}}{\D}$. This can be shown through contradiction. Each vertex in the vertex cover can cover at most $\D$ edges, which in total must exceed $\abs{E}$.
    \end{itemize}
\end{enumerate}

\subsection{Multiplicative approximation}

In example case \ref{subsection:examples}.\ref{listitem:noedges}, the multiplicative approximation must return $0$.  But in example case \ref{subsection:examples}.\ref{listitem:oneedge}, the multiplicative approximation must {\em not} return $0$.  Therefore, to return a multiplicative approximation requires $\Omega(n)$ queries (to distinguish between the two cases), and no sublinear multiplicative approximation is immediately possible.

\subsection{Additive approximation}

There are theoretical results stating that it is computationally hard to approximate a vertex cover to a factor of better than $1.36$ (and maybe even $2$).  Because an additive approximation is even harder than a multiplicative approximation at large input sizes, no sublinear additive approximation is immediately possible.

\subsection{Combined Multiplicative and Additive 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$.
\end{definition}

  By relaxing the multiplicative definition, we avoid the problem of distinguishing 0 edges and 1 edge.  In section \ref{section:sublinearvc}, we prove an $(O(\log \D), \epsilon n)$-approximation for the minimum vertex cover problem.

\section{Local Model for Distributed Algorithms}
\subsection{Overview}
The input to a distributed algorithms problem is a network, consisisting of processors (nodes) connected by links (edges). In the ``local model'', computations run in communication rounds which operate in the following fashion.
\begin{itemize}
  \item Nodes perform computation on their input bits, random bits, received messages, and history of received messages.
  \item Nodes send messages to neighbors. Messages don't necessarily have to be the same.
  \item Nodes receive messages from neighbors.
\end{itemize}
A distributed local algorithm describes computations to perform and messages to send for a node in each round.  For the purposes of this class, we also assume the following properties of the network.
\begin{itemize}
  \item max degree $\Delta$
  \item each processor knows its neighbors
  \item synchronous computation -- processors reliably send messages to each other during synchronized rounds of communication
\end{itemize}

\subsection{Vertex Cover in the local distributed model}

Unlike in parallel algorithms, computation is performed by the communication network \textbf{on} the communication network. In other words, the input graph for the problem is the network itself, where nodes represent processors and edges represent links. 

In the local model, the input to the vertex cover problem is the network graph, and the output for each node is whether it is ``in'' or ``out'' of the vertex cover.
  

\subsection{Connection from fast distributed algorithms to sublinear-time sequential algorithms}
We can simulate the output of any distributed algorithm using a sequential 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 $\leq \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 many incredible $k$-round distributed algorithms for $k$ constant or $\log\log n$.

To simulate the output for vertex $v$ after a $k$-round distributed algorithm, we run $k$ iterations.  In each iteration $i \in \{0, 1, ... k - 1\}$, we sequentially simulate the computation, messages sent, and messages received for each of the nodes in the $\D^{k - i}$ ball surrounding vertex $v$.  Any information calculated at a node $\geq i$ away from $v$ after iteration $i$ will never reach $v$, so does not need to be simulated.  Finally, we simulate vertex $v$.

This idea is formalized in the \textbf{Parnas-Ron Framework} for reducing distributed to sequential algorithms, which is applied to the Vertex Cover problem in section \ref{section:parnasron}.

\section{Sublinear-time algorithm for Vertex Cover}\label{section:sublinearvc}

\subsection{Distributed Subroutine}
Now, we go over a distributed algorithm that returns a valid vertex cover as described in section \ref{section:vertexcover}.
\begin{algorithm}[!ht]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
  \Input{Graph $G=(V,E)$}
  \Output{Approximated vertex cover $A$}
  $i \gets 0$ \;
  $A \gets \emptyset$ \;
  \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!30!white}}
        \tikzset{round2/.style={state,
                                    minimum size=0.5cm,
                                    line width=0.5mm,
                                    fill=blue!30!white}}
        \tikzset{round3/.style={state,
                                    minimum size=0.5cm,
                                    line width=0.5mm,
                                    fill=green!50!white}}
        \tikzset{round1/.style={state,
                                    minimum size=0.5cm,
                                    line width=0.5mm,
                                    fill=orange!50!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,blue!30!white] (a) -- (2a);
        \draw[thick, line width=0.5mm,blue!30!white] (a) -- (2b);
        \draw[thick, line width=0.5mm,blue!30!white] (b) -- (2a);
        \draw[thick, line width=0.5mm,blue!30!white] (b) -- (2b);
        \draw[thick, line width=0.5mm,blue!30!white] (c) -- (2a);
        \draw[thick, line width=0.5mm,blue!30!white] (c) -- (2b);
        \draw[thick, line width=0.5mm,blue!30!white] (d) -- (2a);
        \draw[thick, line width=0.5mm,blue!30!white] (2b) -- (3b);
        \draw[thick, line width=0.5mm,green!50!white] (3b) -- (3a);
        \draw[thick, line width=0.5mm,orange!50!white] (3a) -- (1b);
        \draw[thick, line width=0.5mm,blue!30!white] (2b) -- (1a);
        \draw[thick, line width=0.5mm,orange!50!white] (2b) -- (1a);

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

        \draw[thick, line width=0.5mm,orange!50!white] (1b) -- (2.5, 3);
        \path (2.5, 3) -- node[auto=false,,orange!50!white]{\Huge \vdots} (2.5, 5);
        \draw[thick, line width=0.5mm,orange!50!white] (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$. Then, the orange edges to be removed.  For example, this leads to one of the green nodes being bumped down to degree 1.

In round 1, the blue nodes and edges, with degree 4, are added to $A$.  In round 2, no modifications are made (since no remaining nodes have updated degree two or more). In round 3, the green nodes, now only connected to one another, are both added to $A$ and the green edge is removed.

After the algorithm terminates at $\log_2 \D = 4$ rounds, each node will know if it is in $A$.

\begin{claim}    \label{claim:terminate}
Algorithm \ref{alg:distr} terminates in $\log_2\D$ rounds.
\end{claim}
\begin{proof}
The degree threshold for removing nodes $\frac{\D}{2^i}$ becomes less than one after $i = \log_2\D$ rounds.  Since any nodes of degree less than one have no edges, all edges will have been removed, and the algorithm will have terminated.
\end{proof}

\begin{claim}    \label{claim:valid}
$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$ by the algorithm's design.
\end{proof}

\begin{claim}Let $\theta$ be any vertex cover of graph $G$. Each round of Algorithm \ref{alg:distr} adds $\leq 2\abs{\theta}$ new nodes to the outputted vertex cover that are not in $\theta$.
    \label{claim:competitive}
\end{claim}
\begin{proof}
Let $\D$ denote the maximum degree of a node in $G$.  Let $V_i$ denote the set of all nodes remaining at the start of round $i$, and let $R_i = V_{i+1} \setminus V_i$ denote the set of all nodes to be removed in round $i$.

At the start of the $i$th round, every node in $V_i$ has a maximum updated degree $\leq \frac{\D}{2^{i-1}} = 2 \cdot \frac{\D}{2^i}$, because larger degree nodes would have been removed in an earlier iteration.  Furthermore, every node in $R_i$ has a minimum updated degree $\geq \frac{\D}{2^i}$ by the design of the algorithm.

Let $X_i = R_i \setminus \theta$ be the set of nodes removed in round $i$ that are {\em not} in $\theta$, and let $E_{X_i}$ be the set of edges touching $X_i$.

The nodes in $R_i$ have minimum updated degree $\geq \frac{\D}{2^i}$, so \begin{equation}\abs{E_{X_i}} &\geq \frac{\D}{2^i} \abs{X_i}.\label{eqn:lowerbound}\end{equation}

Since $\theta$ is a vertex cover, every edge in $E_{X_i}$ must have an endpoint in $\theta$.  In order for all edges in $E_{X_i}$ to have an endpoint in $\theta$, the number of such edges cannot exceed the total degree of the remaining nodes in $\theta$.  The updated degree of {\em any} remaining node is at most $2 \cdot \frac{\D}{2^i}$, so \begin{equation} \abs{E_{X_i}} \leq 2\cdot \frac{\D}{2^i} \abs{\theta \cap V_i} \leq 2 \cdot \frac{\D}{2^i}\abs{\theta}.\label{eqn:upperbound}\end{equation}

Using the transitivity of inequality on equations \ref{eqn:lowerbound} and \ref{eqn:upperbound}, \begin{equation}\frac{\D}{2^i} \abs{X_i}\leq 2 \cdot \frac{\D}{2^i}\abs{\theta}\end{equation} \begin{equation}\abs{X_i}\leq 2 \abs{\theta}\end{equation}

\end{proof}

\begin{theorem}
Let $\theta$ be any optimal 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}
The validity of the vertex cover follows from claims \ref{claim:terminate} and \ref{claim:valid}, and the statement that $\abs{\theta} \leq \abs{A}$ follows from the optimality of $\theta$.

The proof that $\abs{A} \leq (1+2\log \D)\abs{\theta}$ follows from claim \ref{claim:competitive}.  If each round adds at most $2\abs{\theta}$ nodes not in $\theta$, then the algorithm adds at most $\log \D \cdot 2\abs{\theta}$ extra nodes to $A$ overall, and the total number of nodes in the outputted vertex cover is at most $\abs{\theta} + \log \D \cdot 2\abs{\theta}$.
\end{proof}

The distributed algorithm achieves a $O(\log \D)$ approximation in simulated $O(\D^{\log \D})$ queries.

\subsection{Using Parnas-Ron Framework}\label{section:parnasron}

The \textbf{Parnas-Ron framework} samples nodes, simulates the distributed algorithm to find the output of those nodes, and extrapolates and estimates using the simulation results. We pick a sample size $r$ based on the desired $\epsilon$ approximation precision. Using Chernoff, we require $r=O(\frac{1}{\epsilon^2})$.

The following is an application of the Parnas-Ron framework to the problem of Approximate Vertex Cover.

\begin{algorithm}[!ht]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
  \Input{Graph $G$, $\epsilon$}
  \Output{the estimated size $\hat v$ of the minimum vertex cover of $G$}
  $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}

The overall runtime is $O(r\D^{\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.

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}