%\documentclass[slidestop,compress,mathserif,blue]{beamer}
\documentclass[compress,blue]{beamer}
\mode<presentation>
%\usepackage[bars]{beamerthemetree} % Beamer theme v 2.2
\usetheme{Warsaw} % Beamer theme v 3.0
%\usecolortheme{lily} % Beamer color theme
\usefonttheme{default}
\usepackage{listings}
\usepackage{biblatex}
\bibliography{bibs}
\title{Algortithms for the Min-Cut problem}
\author{Hongwei Jin}
\institute{Department of Applied Mathematics\\ Illinois Insititute of Technology}

\hypersetup{pdfpagemode=FullScreen} % makes your presentation go automatically to full screen

% define your own colors:
\definecolor{Red}{rgb}{1,0,0}
\definecolor{Blue}{rgb}{0,0,1}
\definecolor{Green}{rgb}{0,1,0}
\definecolor{magenta}{rgb}{1,0,.6}
\definecolor{lightblue}{rgb}{0,.5,1}
\definecolor{lightpurple}{rgb}{.6,.4,1}
\definecolor{gold}{rgb}{.6,.5,0}
\definecolor{orange}{rgb}{1,0.4,0}
\definecolor{hotpink}{rgb}{1,0,0.5}
\definecolor{newcolor2}{rgb}{.5,.3,.5}
\definecolor{newcolor}{rgb}{0,.3,1}
\definecolor{newcolor3}{rgb}{1,0,.35}
\definecolor{darkgreen1}{rgb}{0, .35, 0}
\definecolor{darkgreen}{rgb}{0, .6, 0}
\definecolor{darkred}{rgb}{.75,0,0}

\xdefinecolor{olive}{cmyk}{0.64,0,0.95,0.4}
\xdefinecolor{purpleish}{cmyk}{0.75,0.75,0,0}

% can also choose different themes for the "inside" and "outside"

% \usepackage{beamerinnertheme_______}
% inner themes include circles, default, inmargin, rectangles, rounded

% \usepackage{beamerouterthemesmoothbars}
% outer themes include default, infolines, miniframes, shadow, sidebar, smoothbars, smoothtree, split, tree

\useoutertheme[subsection=false]{smoothbars}

% to have the same footer on all slides
%\setbeamertemplate{footline}[text line]{STUFF HERE!}
\setbeamertemplate{footline}[text line]{} % makes the footer EMPTY

% include packages
\usepackage{subfigure}
\usepackage{multicol}
\usepackage{amsmath}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage[all,knot]{xy}
\xyoption{arc}
\usepackage{url}
\usepackage{multimedia}
\usepackage{hyperref}
\footnotesize
\begin{document}
\frame{
	\titlepage}
\section{Introduction} % Bookmark information

	\begin{frame}
	\frametitle{Outline}
	\tableofcontents
	\end{frame}
	
	\subsection{Problem Definition} % Bookmark information
	
	\begin{frame}[c]
	\frametitle{Problem Definition}
	Let $ G = (V,E) $ be undirected graph with $ n $ vertices, and $ m $ edges. We are interested in the notion of a cut in a graph.
	\begin{definition}
	A \textbf{cut} in $ G $ is a partiontion of the vertices of $ V $ into two sets $ S $ and $ T $, $ T=V(G)\backslash S $, where the edges of the cut are \[ (S,T)=\{ uv|u\in S, v \in T,S\cap T=V(G), uv\in E(G) \} \]
	where $ S \neq \emptyset $ and $  T \neq \emptyset $. We will refer to the number of edges in the cut $ (S,T) $ as the \textit{size} of the cut.
	\end{definition}
	
	\end{frame}
	
	\begin{frame}[c]
	\frametitle{Problem Definition}
	We are intersted in the problem of computing the \textbf{minimum cut}, that is, the cut in the graph with minimum cardinality.
	\begin{description}
	\item [\textit{s-t minimum cut}] Require that the two specific vertices $ s $ and $ t $ be on opposite sides of the cut
	\item [\textit{gloable minimum cut}] No such requirement.
	\end{description}
	\end{frame}
	
	\subsection{Previous Works}
	\begin{frame}[c]
	\frametitle{Previous Works}
	The oldest known way to compute min-cut is to use their well known duality with max-flow \footfullcite{ford1956maximal}. Now we should recall some definition and theorem from graph theorem.
	\begin{theorem}[Max-flow Min-cut Theorem (Ford and Fulkerson,1956)] 
	In every network, the maximum value of a feasible flow eqauls the minimum capacity of a source/sink cut.
	\end{theorem}
	For an example
	\begin{figure}[h]
	\centering
	\includegraphics[width=0.4\linewidth]{./ex08}
%	\caption{Max-flow Min-cut example}
	\label{fig:ex08}
	\end{figure}
	\end{frame}

	\begin{frame}[c] % Cover slide
	\frametitle{Previous Works}
	The best known sequential time bound is $ O(mn \log (n^2/m)) $, which is found by Glodberg and Tarjan \footfullcite{goldberg1988new} using Ford-Fulkerson algorithm.
		
	\vspace{2em}	
	Hao and Orlin algorithm shows how the max-flow computations can be pipelined so that together they take no more time than a single max-flow computation, requiring $ O(mn \log(n^2/m)) $ \footfullcite{hao1994faster}.
	\end{frame}
	
	\begin{frame}[c]
	\frametitle{Previous Work}
	Gabow algorithm shows how to find the edge-connectivity c of a graph in time $ O(cn\log(n^2/m)) $, c denotes the min cut \footfullcite{gabow1991matroid}.
	
	\vspace{2em}
	Algorithm developed by Nagamochi and Ibaraki is designed for weighted graph, undirected graphs. They showed it can be runned in time $ O(mn+n^2\log(n)) $ \footfullcite{nagamochi1992computing}.
	\end{frame}
	
\section{Karger's Algorithm}
	\subsection{Contraction Algorithm}
	 
	\begin{frame}[c]
	\frametitle{Karger's Algorithm}
	The fundamental concept of Karger's Algorithm is "contraction(edge contraction)"
	\begin{definition}
	In a graph $ G $, \textbf{contraction} of edge $ e $ with endpoints $ u,v $ is the replacement of $ u $ and $ v $ with single vertex whose incident edges are the edges other than $ e $ that were incident to $ u $ or $ v $. the resulting graph,denoted as $ G/e $.
	\end{definition}
	
	\pause
	\vspace{2em}
	\begin{columns}
		\begin{column}{0.2\textwidth}
			\centering
			\includegraphics[width=\linewidth]{./ex02}
			\label{fig:ex02}
		\end{column}
		~
		\begin{column}{0.2\textwidth}
			\centering
			\includegraphics[width=\textwidth]{./ex03}
			\label{fig:contract xy}
		\end{column}
		~
		\begin{column}{0.2\textwidth}
			\centering
			\includegraphics[width=\textwidth]{./ex04}
			\label{fig:after contraction}
		\end{column}
	\end{columns}
	\end{frame}
	
	\begin{frame}[c]
	\frametitle{Karger's Algorithm}
	\fbox{\begin{minipage}{10cm}
		\textbf{procedure} MinCut ($ G=(V,E) $)\\
		\indent  \textbf{while} $ |V|>2 $\\
		\indent  choose $ e\in E $ uniformly and random\\
		 $ G\rightarrow G/e $\\
		\textbf{return} the only cut in $ G $
		\end{minipage}	}
	\pause
	\vspace{2em}
	\begin{figure}[h]
	\centering
	\includegraphics[width=0.5\linewidth]{./ex06}
	\label{fig:ex06}
	\end{figure}
	
	\begin{figure}[h]
	\centering
	\includegraphics[width=0.5\linewidth]{./ex07}
	\label{fig:ex07}
	\end{figure}
	\end{frame}
	
	\begin{frame}[c]
	\frametitle{Karger's Algorithm}
	\begin{block}{Obvervation}
	The size of the minimum cut in $ G/e $ is at least as large as the minimum cut in $ G $ (as long as $ G/e $ has at least one edge). Since any cut in $ G/e $ has a corresponding cut of the same cardinality in $ G $.
	\end{block}
	\pause
	\begin{block}{Obvervation}
	Let $ e_1,...e_{n-2} $ be a sequence of edges in $ G $, such that none of them is in the minimum cut, and such that $ G'=G/{ e_1,...e_{n-2}} $ is a single multi-edge. Then, this multi-edge correspond to the minimum cut in G.
	\end{block}
	\pause
	\begin{block}{Obvervation}
	The algorithm always output a cut, and the cut is not smaller than the minimum cut.
	\end{block}
	\end{frame}
	\subsection{Algorithm Analysis}
	\begin{frame}[c]
	\frametitle{Algorithm Analysis}
	
	\begin{block}{Lemma}
	A cut $ (S,T) $ is output by the MinCut algorithm if and only if no edge crossing $ (S,T) $ is contracted by the algorithm.
	\end{block}
	\pause
	\begin{block}{Lemma}
	If a graph $ G $ has a minimum cut of size $ k $, and it has n vertices, then $ |E(G)|\geq \frac{kn}{2} $
	\end{block}
	\pause
	\begin{block}{Lemma}
	If we pick in random an edge e from a graph G, then with probability at most 2/n it belong to the minimum cut.
	\end{block}
	\pause
	\begin{block}{Lemma}
	MinCut algorithm runs in $ O(n^2) $ time.
	\end{block}
	\end{frame}
	
	\begin{frame}[c]
	\frametitle{Algorithm Analysis}
	\begin{theorem}
	MinCut algorithm outputs the min cut in probability $ \mathbb{P}\geq \frac{2}{n(n-1)} $
	\end{theorem}
	\begin{proof}
	Let $ x_i $ be the event that edge $ e_i $ is not in the minimum cut of $ G_i $. If the MinCut algorithm output a minimum cut, then all the event sequence $ \{ x_0,...x_{n-3} \} $ will happen. Since at most with probability $ 2/n $ the edge will belong to the minimum cut. Thus we have the probability at least \[ (1-\frac{2}{n})(1-\frac{2}{n-1})...(1-\frac{2}{3})=(\frac{n-2}{n})(\frac{n-3}{n-1})...(\frac{1}{3})=\frac{2}{n(n-1)} \]
	\end{proof}
	\end{frame}
	
	\begin{frame}[c]
	\frametitle{Algorithm Analysis}
	\begin{block}{Lemma}
	The probability that repeat MinCut algorithm $ T={n \choose 2}\log n $ times fails to return the minimum cut is $ <\frac{1}{n} $
	\end{block}
	\begin{proof}
	The probability of failure is at most\[  (1-\frac{2}{n(n-1)} )^{{n \choose 2}\log n} \leq  \exp(-\log n)=\frac{1}{n} \]
	\end{proof}
	\end{frame}
	
	\begin{frame}[c]
	\frametitle{Algorithm Analysis}
	\begin{theorem}
	In $ O(n^4 \log n) $ time the minimum cut is returned with high probability.
	\end{theorem}
	\end{frame}	
	
\section{Karger-Stein Algorithm}
	\subsection{Recursive Contraction Algorithm}
	\begin{frame}[c]
	\frametitle{Karger-Stein Algorithm}
	
	\begin{block}{Obvervation}
	As the graph get smaller, the probability to make a bad choice increases. So, run the algorithm more times when the graph is smaller.
	\end{block}
	\vspace{2em}
	\pause
	\fbox{\begin{minipage}{10cm}
		\textbf{procedure} MinCut ($ G,\textbf{t}$)\\
		\indent  \textbf{while} $ |V|>\textbf{t} $\\
		\indent  choose $ e\in E $ uniformly and random\\
		$ G\rightarrow G/e $\\
		\textbf{return} the only cut in $ G $
		\end{minipage}	}
	\end{frame}
	
	\begin{frame}[c]
	\frametitle{Karger-Stein Algorithm}
	\begin{block}{Lemma}
	The probability that MinCut$ (G,n/\sqrt{2}) $ had NOT contracted the minimum cut is at least 1/2.
	\end{block}
	\begin{proof}
	Let $ l=n-t=n-\lceil 1+n/\sqrt{2} \rceil $, we will get  \[ \mathbb{P}[x_0\cap ... \cap x_{n-t}] \geq \frac{t(t-1)}{n(n-1)}= \frac{(\lceil 1+n/\sqrt{2} \rceil)(\lceil 1+n/\sqrt{2} \rceil-1)}{n(n-1)} \geq \frac{1}{2} \]
	\end{proof}
	\end{frame}
	
	\begin{frame}[c]
	\frametitle{Karger-Stein Algorithm}
	They introduced a recursive way to find the minimum cut
	\vspace{2em}
	
	\fbox{\begin{minipage}{10cm}
	\textbf{procedure} FastMinCut (G)\\
				\textbf{if} $ |V| < 6 $\\
					MinCut(G,2)\\
				\textbf{else}\\
					$ t = 1+|V|/sqrt(2) $\\
					G1 = MinCut(G,t)\\
					G2 = MinCut(G,t)\\
				\textbf{return} min (FastMinCut(G1), FastMinCut(G2))
	\end{minipage}}
	\end{frame}

	\subsection{Algorithm Analysis}
	\begin{frame}[c]
	\frametitle{Algorithm Analysis}
	\begin{theorem}
			The running time of FastMinCut(G) is $ O(n^2 \log n) $, where $ n=|V(G)| $.
	\end{theorem}
	\begin{proof}
			Well, we perform two calls to MinCut(G,t) which takes $ O(n^2) $ time. And then we perform two recursive calls, on the resulting graphs. We have:\[ T(n)=O(n^2)+2T(\frac{n}{\sqrt{2}}) \]
			The solution to this recurrence is $ O(n^2 \log n) $ as one can easily verify.
	\end{proof}
	\end{frame}
	
	\begin{frame}[c]
	\frametitle{Algorithm Analysis}
	\begin{theorem}
		Running FastMinCut finds the minimum cut with probability larger that $ \frac{2\log 2}{\log n}$,which can be notated as $ \Omega(1/\log n) $
	\end{theorem}
	\small The probability to succeed in the first call on $ G_1 $ is the probability that contract did not hit the minimum cut (this probability is larger than 1/2), times the probability that the algorithm succeeded on $ G_1 $ in the recursive call (those two events are independent). Thus, the probability to succeed on the call on $ G_1 $ is at least $ \frac{1}{2}P(\frac{n}{\sqrt{2}}) $. Thus, the probability to fail on $ G_1 $ is $ \leq 1-\frac{1}{2}P(\frac{n}{\sqrt{2}}) $.
	
	The probability to fail on both $ G_1 $ and $ G_2 $ is smaller than \[ (1-\frac{1}{2}P(\frac{n}{\sqrt{(2)}}))^2 \]
	And thus, the probability for the algorithm to succeed is \[ P(n)\geq 1-(1-\frac{1}{2}P(\frac{n}{\sqrt{(2)}}))^2 = P(\frac{n}{\sqrt{(2)}})-\frac{1}{4}(P(\frac{n}{\sqrt{(2)}}))^2 \]
	\end{frame}

	\begin{frame}[c]
	\frametitle{Algorithm Analysis}
	\begin{theorem}
		With high probability we can find all min cuts in the running time of $ O(n^2 \log^3n) $.
	\end{theorem}
	\begin{proof}
		Since We know that $ P(n)=O(\frac{1}{\log n}) $, therefore after running this algorithm $ O(\log^2 n) $ times, the probability of missing a specific min-cut is \[ \mathbb{P}=(1-P(n))^{O(\log^2n)} \leq (1-\frac{c}{\log n})^{3\log^2 n/c} \leq \exp(-3\log n) = \frac{1}{n^3} \]
		And there are at most $ {n \choose 2} $ min-cuts, hence the probability of missing any min-cut is\[ \mathbb{P}[\mathrm{miss\ any\ min-cut}] \leq {n \choose 2}\frac{1}{n^3} = O(\frac{1}{n}) \].
		Thus the probability of success is large as n is large enough.
	\end{proof}
	\end{frame}
	
\section{Implementation}
%	\subsection{Implementation}
	\begin{frame}[c]
	\frametitle{Example}
	\begin{figure}[h]
		\centering
		\includegraphics[width=0.3\linewidth]{./Untitled-2.png}
		\label{fig:200-vertices simple graph}
	\end{figure}

	\fbox{\begin{minipage}{10cm}
	Total edges: 2517\\
	Total vertices: 200\\
	Maximum degree: 39\\
	Minimum degree: 20\\
	average degree: 25\\
	Mincut is \textbf{17}
	\end{minipage}}	
	\end{frame}
	
	\begin{frame}[c]
	\frametitle{Karger's Algorithm}
	\begin{figure}
	\centering
	\tiny
	\lstset{language=python}
		\lstinputlisting[firstline=5,lastline=25]{./NewKargerMinCut.py}
	\dots
	\lstset{language=python}
			\lstinputlisting[firstline=71,lastline=76]{./NewKargerMinCut.py}
	\end{figure}
	\end{frame}
	
	\begin{frame}[c]
		\frametitle{Result}
	\begin{figure}[h]
	\centering
	\includegraphics[width=0.8\linewidth]{./Untitled-1}
	\label{fig:Untitled-1}
	\end{figure}
	\vspace{2em}
	It gets the number of edges between vertex set $ S,T $ is \textbf{17}.
	\end{frame}
	
	\begin{frame}[c]
	\frametitle{Karger-Stein Algorithm}
	For Karger-Stein Algorithm
	\begin{figure}
		\centering
		\tiny
		\lstset{language=python}
			\lstinputlisting[firstline=28,lastline=39]{./NewKargerMinCut.py}
		\dots
		\lstset{language=python}
			\lstinputlisting[firstline=80,lastline=85]{./NewKargerMinCut.py}
	\end{figure}
	It will get the same result as Karger's algorithm.
	\end{frame}
	
\section{Conclusion}
	\subsection{Summing up}
	
	\begin{frame}[c]
	\frametitle{Summing up}
	Comparision of Karger's algorithm and Karger-Stein algorithm.
		\begin{center}
		\begin{tabular}{ l || c | c }
		    \hline
		    \textbf{Bound}  & \textbf{Karger algorithm} & \textbf{Karger-Stein algorithm} \\ \hline
		    Probability & $ O(1/n^2) $ & $ O(1/\log n) $    \\ \hline
		    Cost & $ O(n^2) $ & $ O(n^2\log n) $ \\ \hline
		    Running times & $ {n \choose 2}\log n $ & $  \log^2 n $ \\ \hline
		    Totol Order & $ O(n^4\log n) $  & $ O(n^2 \log^3 n) $ \\
		    \hline
		\end{tabular}
		\end{center}
	\end{frame}
	
	\subsection{Improvement}
	\begin{frame}[c]
	\frametitle{Improvement}
	\begin{itemize}
	\item Parallel Algorithms
		\begin{itemize}
			\item The parallel version of contraction algorithm $ \mathcal{RNC} $ runs in polylogarithmic time using $ n^2 $ processors on a PRAM\footfullcite{karger1996new}.
		\end{itemize}
	\pause
	\item Random Algorithems
		\begin{itemize}
		\item Timo Kötzing et al. apply "Ant colony optimization method" can obtain the solution in expected polynomial time\footfullcite{kotzing2010ant}.
		\item Frank Neumann et al. apply "Randomized Search Heuristics" method to obtain the solution in expected polynomial time\footfullcite{neumann2011computing}.
		\end{itemize}
	\end{itemize}
	\end{frame}
	
	\begin{frame}[c]
	\frametitle{Further Reading}
	
	Classical textbook: \textit{Randomized Algorithms} \footfullcite{motwani1995randomized}.\\
	\vspace{2em}
	An supplementary reading material is class notes organized by Sariel Har-Peled\footfullcite{har2005class}.\\
	\vspace{2em}
	There is a paper analysis most recent algorithm to find min-cut by conducting experimental evaluation the relative performance of these algorithms {\footnotesize\footfullcite{chekuri1997experimental}}. 
	\end{frame}
	
	\begin{frame}[c]
	\begin{center}
	{\LARGE Thanks}
	\\
	Any Questions?
	\end{center}
	
	\end{frame}
	
\end{document}