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

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\usepackage{tikz}
\usepackage{algorithm}% http://ctan.org/pkg/algorithm
\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx
\usepackage{caption}
\usetikzlibrary{positioning, decorations.text}
\usepackage{wrapfig}
\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{6}{February 25, 2019}{Ronitt Rubinfeld}{Michal Shlapentokh-Rothman}

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

\section{Outline}
Today, we will discuss a general framework for testing minor-free properties by looking at a way to test planarity. 
\begin{itemize}
	\item Problem Setup and Definitions
	\item Algorithm Given Partition Oracle $P$
	\item Implementing Partition Oracle $P$
\end{itemize}

\section{Problem Setup and Definitions}
Our overall goal is to be able to distinguish graphs with a property $P$ from all other graphs in sublinear time. However, there is no (known) method to do this exactly without exploring the whole graph. So, we will make a compromise: can we distinguish graphs with property $P$ from graphs that are $\mathbf{\epsilon}$\textbf{-far} away from having property $P$?
\begin{figure}[!h]
\centering
\begin{tikzpicture}
\node[circle, minimum size=6cm, draw, fill=red] (a) {};
\node[circle, minimum size=4cm, draw, fill=cyan] (b) {};
\node[circle, minimum size=3cm, draw, fill=green] (c) {};

\draw [decorate, decoration={text along path, text = All graphs}] (110:2.7) arc (110:0:2.7cm); 

\draw [decorate, decoration={text along path, text = {Graphs that are {$\epsilon$}-close to property {$P$}} }] (180:1.7) arc (180:-30:1.7cm); 

\draw [decorate, decoration={text along path, text = Graphs with Property {$P$}} ] (200:1) arc (200:-90:1cm); 

\end{tikzpicture}
\caption{We want to distinguish the line between the blue circle and the red circle}
\end{figure}
We will show how to distinguish such graphs by looking at the property of planarity. First, we will start with several definitions. Note that all graphs have max degree of $d$. 
\begin{definition}
$H$ is a \textbf{minor} of a graph $G$ if we can obtain $H$ from $G$ via vertex removals, edge removals, or edge contractions.
\end{definition}
\begin{figure}[!h]
\centering
\begin{tikzpicture}

\node[circle,minimum size=1.5cm, draw] at (6,0) {};

\node[circle, minimum size=1.5cm ,draw] at (8,0) (B) {};
\draw[line width=2pt] (6.7,0) -- (7.3,0) ;
\draw[line width=2pt] (5.2,0) -- (4.5,0);
\draw[line width=2pt] (5.2,0) -- (4.5,.4);
\draw[line width=2pt] (5.2,0) -- (4.5,-.4);
\draw[line width=2pt] (8.8,0) -- (9.5,0) ;
\draw[line width=2pt] (8.8,0) -- (9.5,.4) ;
\draw[line width=2pt] (8.8,0) -- (9.5,-.4) ;

\node[circle, minimum size=1.5cm, draw] at (14,0) (C) {};
\draw[line width=2pt] (13.3,0) -- (12.5,0);
\draw[line width=2pt] (13.3,0) -- (12.5,.4);
\draw[line width=2pt] (13.3,0) -- (12.5,-.4);
\draw[line width=2pt] (14.7,0) -- (15.5,0);
\draw[line width=2pt] (14.7,0) -- (15.5,.4);
\draw[line width=2pt] (14.7,0) -- (15.5,-.4);

\draw[->,thick] (10,0) -- (12,0);
\end{tikzpicture}
\caption{The graph on the left, is a minor of the graph on the right}
\end{figure}
\begin{definition}
$G$ is $H-minor-free$ if $H$ is not minor of $G$
\end{definition}
\begin{definition}
$G$ is $\epsilon$-close to $H-minor-free$ if can remove $\leq \epsilon dn$ edges to make it $H-minor-free$.  (Otherwise, G is $\epsilon$-far)
\end{definition}
\begin{definition}
For a minor close property $P$, if $G \in P$, then all minors of $G$ are in $P$
\end{definition}
Our goal is to test $H-minor$ freeness which means we want to pass $H-minor$ free graphs and fail graphs that are $\epsilon$-far from $H-minor$ free. The following theorem and definitions will be helpful.
\begin{theorem}[Robertson and Seymour]
Every minor-closed property is expressible as a constant number of excluded minors.
\end{theorem}
Examples of minor-closed properties include $K_{3,3}$ or $K_5$, non-planar graphs and bounded tree width.
\begin{definition}
G is $(\epsilon,k)$-hyperfinite if we can remove $\leq \epsilon n$ edges and remain with connected components of size $\leq k$.
\end{definition}
In other words, we have a $(\epsilon,k)$-hyperfinite graph if we can remove a few edges and break up graph into small components. We can connect the notion of hyperfiniteness to $H-minor$ freeness. 
\begin{theorem}
Given $H$, $\exists$ $C_H$ such that $\forall$ $0<\epsilon<1$, every $H-minor$ free of graph of degree $\leq d$ is $(\epsilon d, \frac{C_{H}^2}{\epsilon ^2})$-hyperfinite. 
\end{theorem}
All of this means that subgraphs of $H-minor$ free graphs are also $H-minor$ free and also hyperfinite. \par
Why is hyperfinitiness useful? We can use it to prove that a graph is $H-minor$ free. We can partition a graph $G$ into $G'$ by removing only a few edges. If non-constant size components remain, then we know that $G$ is \textbf{not} $H-minor$ free. \par
What if $G'$ is $\epsilon$-close to having the property? Then we know that $G$ is $2\cdot \epsilon$-close to having the property. Furthermore, it is particularly easy to test whether $G'$ has the property since we can just pick random components and in constant time test if they have the property. \par
What we need now is is a `local' (sublinear) way to determine $G'$. First, we will assume that we have a `partition oracle' $P$ and then we will construct the partition oracle. \par 
\section{Algorithm Given Partition Oracle}
Our partition oracle will work as follows:
\begin{itemize}
\item Input: vertex $v$
\item Output: $p[v]$ (where $v$ is the partition) name such that $\forall$ $v \in V$ 
\begin{enumerate}
\item $|P[v]| \leq k$
\item $P(v)$ is connected
\end{enumerate}
\end{itemize}
If $G$ is $H-minor$ free, then with probability $\frac{9}{10}$, $|{u,v} \in E|P[u]+P[v]| \leq \frac{\epsilon d}{4}n$. 
In the first half of the algorithm, we are determining if the partition oracle `looks right' meaning are there few crossing edges and in the second part we are testing random partitions.
\subsection{Algorithm}
\begin{algorithm}[H]
\caption{Algorithm with Oracle}
\begin{algorithmic}
\State {$\hat{f}$ number of edges $(u,v)$ such that $P[u] \neq P[v]$ to additive error $\leq \frac{\epsilon dn}{8}$ }
\If {$\hat{f} > \frac{3}{8} \epsilon dn$}
	output fail and halt
\EndIf
\State Choose $S=\mathcal{O}(\frac{1}{\epsilon})$ random nodes 
	\For {$s \in S$}
		\If {$P[s] \geq K$ or $P[s]$ is not $H-minor$ free}
			\State reject and halt. 
		\EndIf
	\EndFor
 \State Accept 
\end{algorithmic}
\end{algorithm}
The first part of the algorithm (the part before the choose statement), makes $\mathcal{O}(\frac{1}{\epsilon ^2})$ calls to the oracle. The second part, makes $\mathcal{O}(\frac{d}{\epsilon ^2})$ calls to the oracle, making the total number of calls $\mathcal{O}(\frac{d}{\epsilon ^3})$
 
\subsection{Analysis}
If $G$ is $H-minor$ free:
\begin{itemize}
\item We know that if $G$ is $H-minor$ free, then we will not halt on the first half of the algorithm because $E[\hat{f}] \leq \frac{\epsilon dn}{4}$ and with sampling bounds $\hat{f} \leq \frac{\epsilon dn}{4} +\frac{\epsilon dn}{8} = \frac{3}{8}\epsilon dn$.
\item Since, our oracle produces $H-minor$ free graphs we can say $\forall s \in V$, $P[s]$ is $H-minor$ free. 
\end{itemize}
We see that our algorithm works when $G$ is $H-minor$ free. Let us now analyze what happens when $G$ is $\epsilon$-far from $H-minor$ free.
\begin{itemize}
	\item Case $1$:$P$'s output does not satisfy $|\{(u,v) \in E : P(u) \neq P(v)\}| < \frac{\epsilon dn}{2}$. Using out sampling bounds, we can say that $\hat{f} > \frac{\epsilon dn}{2} - \frac{\epsilon dn}{8}=\frac{3}{8}\epsilon dn$ which means the algorithm will out put `fail' with probability $\geq \frac{9}{10}$. 
	\item Case $2$: $P$'s output does satisfy $|\{(u,v) \in E : P(u) \neq P(v)\}| < \frac{\epsilon dn}{2}$ . This means that $G'$ can be created from $G$ with edges in $C$ removed. It is important to note that if $G'$ is $\frac{\epsilon}{2}$-close to $G$, This means that if $G$ is $\epsilon$-far from aving a property, then $G'$ is $\frac{\epsilon}{2}$-far from having the property. Since $G'$ is $\frac{\epsilon}{2}$-far from $H-minor$ free, we much change $\geq \frac{\epsilon dn}{2}$ edges to make it $H-minor$ free, which touch at least $\frac{\epsilon n}{2}$ nodes. So with probability $\geq \frac{\epsilon}{2}$, we will pick a node in a component which is not $H-minor$ free.
\end{itemize}
We now need to implement the partition oracle $P$.
\section{Implementing Partion Oracle}
We will implement our partion oracle by first defining a global partitioning stragety that does not work in sublinear time and then figuring out how to implement the strategy locally. 
\subsection{Global Partitioning Strategy}
We will first define a useful concept known as an isolated neighborhood.
\begin{definition}
$S$ is $(\delta,k)$-isolated neighborhood of node $v$ if:
\begin{itemize}
	\item $v \in S$
	\item $S$ is connected
	\item $|S| \leq k$
	\item Number edges connecting $S$ and $\overline{S}$ is $\leq \delta|S|$.
\end{itemize}
\end{definition}
In hyperfinite graphs, most nodes have $(\delta,k)$-isolated nodes. Why? Because if $G$ is hyperfinite, then we know that there exists some partitioning. However, we need there to be a partitioning for the remaining graph since an algorithm may find a different partition. Luckily, we know that no matter what was removed, due to $H-minor$ free properties, we still have an $H-minor$ free graph that is still hyperfinite. 
\begin{algorithm}[H]
\caption{Global Partitioning Algorithm}
\begin{algorithmic}
\State $\pi_1,...,\pi_n$ be nodes in a random order
$p=\phi$
\For {$i=1..n$}
	\If {$\pi_i$ still in graph},
		\If {$\exists (\delta,k)$-isolated neighborhood of $\pi_i$ in remaining graph.}
			\State $S$=this neighborhood
		\Else 
		\State $S=\{\pi_i\}$
		\EndIf
		\State $P=P \cup \{S\}$
		\State Remove $S$ and adjacent edges from graph
	\EndIf
\EndFor
\end{algorithmic}
\end{algorithm} 
We know that if $S$ is $(\delta,k)$-isolated, then it will contribute $\leq \delta |s|$ edges, which overall means $\leq \delta n$. However, we cannot say the same if $S=\{ \pi_i\}$ (one node). But we can show that we will not have too many of these singleton cases. 
\begin{lemma}
If $G'$ is a subgraph of a (hyperfinite) graph $G$ such that $G'$ has $\geq \delta n$ nodes, then $\leq \frac{\epsilon}{30}$ fraction of nodes in $G'$ do not have $(\epsilon,k)$-isolated neighborhoods. 
\end{lemma}
The idea for this proof is that since $G$ is $H-minor$ free, then $G'$ is $H-minor$ free, meaning $G'$ is hyperfinite as well. This means there exists a partition such that most nodes in $G'$ are in $(\delta,k)$-isolated neighborhoods. This means that with a high probability, a random $\pi_i$ will be in a $(\delta,k)$-isolated neighborhood.
\subsection{Local Simulation of Partitioning Oracle}
We will input $v$, assume access to a random function $\pi(v)$ such that $\pi:v \rightarrow [n]$ and then we will output $P[v]$.
\begin{algorithm}[H]
\caption{Local Simulation}
\begin{algorithmic}
\ForAll  {$w$ such that $\pi(w) <\pi(v)$ and $w$ is distance $\leq 2k$ from $v$}
	\State recursively compute $P[w]$
	\If {$\exists w$ such that $v \in P[w]$} 
		\State P[v]=P[w]
	\Else  
	\State look for $(\delta,k)$-isolated neighborhood of $v$ (ignoring nodes which are in $P[w]$ for smaller ranked $w$s)
		\If   {find one}
			\State $P[v]$= neighborhood
		\Else 
			\State $P[v]=\{v\}$
		\EndIf
	\EndIf
\EndFor
\end{algorithmic}
\end{algorithm}
This algorithm makes $d^{\mathcal{O}(k)}$ recursive calls. However, with the bounds we learned in the previous lecture, the runtime is $2^{d^{O(k)}}$. The best possible runtime right now is $d^{\mathcal{O}(\log^2 (\frac{1}{\epsilon}))}$.
\end{document}



