\documentclass[10pt]{article}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}


\usepackage[ruled,vlined,linesnumbered]{algorithm2e}
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{automata,positioning}
\usetikzlibrary{decorations.pathmorphing,shapes}
\usepackage{amssymb}
\usepackage{amsmath, float}


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

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

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{5}{February 20, 2019}{Ronitt Rubinfeld}{Shiyin Wang}

%%%% body goes in here %%%%


\section{Outline}

\begin{itemize}
\item Relationship between Greedy Algorithm and Sublinear Algorithm through Maximal Matching
\item Property Testing
\end{itemize}

\section{Maximal Matching}

\subsection{Definition}

\begin{define}[Maximal Matching]
$M\subset E$, s.t. 
\begin{enumerate}
\item No 2 edges in M share an endpoint 
\item $\forall (u, v)\in E\setminus M$, either u or v is matched by M
\end{enumerate}
\end{define}

We have to emphasis that the matching we discussed in this lecture is maximal, not maximum. Maximum matching is a NP-hard problem.

\subsection{Relationship to Vertex Cover}

It is interesting that the answers of these two graph problem can be bounded by each other. Specifically,

\begin{equation}
\#Maximal\ Matching\leq \#Minimum\ Vertex\ Cover\leq 2 \#Maximal\ Matching
\end{equation}

According to the definition of maximal matching, if we choose all the two nodes in a maximal matching to cover the graph, then it is a vertex cover. Because every edge in $E\setminus M$ has one endpoint in $M$.

On the other hand, just consider covering the edges in the $M$. Because such edges don't share an endpoint, obviously we need to choose one endpoint of this edges to be the cover vertex. Thus the number of cover vertex chosen should be no smaller than the number of edges in a maximal matching.

\subsection{Greedy Algorithm and Oracles}


\begin{algorithm}[H]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
  \Input{Graph $G = (V, E)$}
  \Output{Maximal Matching $M$}
  $M\leftarrow \emptyset$\;
  \For{$(u, v)\in E$} 	
    {\If{Neither $u$ or $v$ previously matched in $M$}
      {Add $e$ to $M$}}
  Return $M$
    \caption{Greedy Algorithm for Maximal Matching}
    \label{alg:1}
\end{algorithm}



This algorithm seems to be very simple and correct, right? But there are two things we need to consider: The first one is what is the order of iterate all the edges in $E$? The second one is how can we check whether an edge is in M? For the first oracle, we can rank the edges in an arbitrary order.

\subsection{Oracle Reduction Framework}
A general approach of making this problem sub-linear is to sample a portion of data and calculate the size of maximal matching and scale the result to the whole graph, as we did in previous lectures. It seems to be obvious but actually we need an oracle to check whether edge $(v, w)$ is in $M$, which we will discuss in the following section.


\begin{algorithm}
\caption{Maximal Matching}
\State $S \leftarrow \frac{8}{\epsilon^2} \textit{ random chosen nodes}$\;
\For {$v \in \mathcal S$}{
$x_v \gets 0$\;
\For{$\forall w \in Neighbor(V)$}{\If {$(v, w) \in M$}{ $x_v \gets 1$}}}
\State $\textbf{Output: }\frac{n}{2S}\sum_{v \in S}^{} (x_v)} + \frac{\epsilon n}{2}$
\end{algorithm}


\subsection{Implementing the Oracle}

Under the sub-linear framework, it is impossible to store all the edges in a list/set and refer to it every time. Luckily, we have a clever approach given the edge selection order.


\begin{algorithm}[H]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
  \Input{Graph $G = (V, E)$}
  \Output{Maximal Matching $M$}
  $M\leftarrow \emptyset$\;
  \For{$(u, v)\in E$} 	
    {\If{Neither $u$ or $v$ previously matched in $M$}
      {Add $e$ to $M$}}
  Return $M$
    \caption{Check whether $e\in M$}
    \label{alg:2}
\end{algorithm}

% Considering the edge rank, the edge in M has another nice property: All the edges adjacent to its two endpoints with lower ranks are not in $M$.

If a edge has the minimal rank among all the edges adjacent to its two endpoints, then it is in $M$.

Given an edge, we can do tree search on all its two endpoints. If the edge has the lowest rank then we stop this branch. Otherwise, continue to search along the edges with lower rank.


\begin{claim}
To check whether a specific edge $e$ is in $M$, the expected number of queries is $2^{O(d)}$ in our algorithm.
\end{claim}
\begin{proof}
Since we run tree search along the two endpoints of $e$, each path has decreasing rank.

$$Pr(path\ of\ length\ k\ has\ decreasing\ order) = \frac{1}{k!}$$

For the graph with bounded degree $d$, there are $(2d)^k$ in each layer. So the total expectation of queries is

$$E[\# queries]  = \sum_{k\geq 1} \frac{(2d)^k}{k!}\leq \frac{e^{2d}}{(k+1)!} = 2^{O(d)}$$

Under bounded degree, the expectation of queries is constant.
\end{proof}



\section{Property Testing}

\begin{define}
Graph G is $\varepsilon-close$ to having property P if we can add/delete no more than $\varepsilon d_{max}n $ edges to get $G'\in P$.
\end{define}

Our goal is to test whether a graph has property $P$ with accurate result $\geq \frac{2}{3}$: $\forall G\in P$, pass $G$; $\forall G$ which is $\epsilon$-far from $P$, we should declare a failure.

\begin{define}[minor]
$H$ is a minor of $G$ if we can obtain $H$ from $G$ through vertex removals, edge removals or edge contractions. Else we can call $G$ is $H$-minor free. 
\end{define}

\begin{define}[minor-closed property]
If $G\in P$, then all minors of $G$ are also in $P$.
\end{define}

\begin{theorem}[Robertson \& Seymour]
Every minor closed property is expressible as constant number of excluded minors.
\end{theorem}

For example, planar graph is equivalent to the absence of $K_5$ and $K_{3, 3}$.

\begin{define}[$(\epsilon, k)$-hyperfinite]
A graph is said to be $(\epsilon, k)$-hyperfinite if we can remove $\leq \epsilon n$ edges such that the graph can be transformed into components which all have size no larger than $k$. $k$ can be a function of $\epsilon$.
\end{define}

This property can be interpreted as we can split the graph into bounded size components after deleting a small fraction of edges.


\end{document}



