\section{Elements of Graphs and Complexity Theory \label{chap:theory}}
\frame{\center \huge Chapter \thesection \\ \vspace{5mm}\alert{\insertsection}}

\begin{frame}{Chapter Content}
	\begin{center}\vfill
		\tableofcontents[sections={\thesection}]
	\end{center}
\end{frame}

\subsection{Combinatorial Optimization}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}


%----------------------------------------------------
\begin{frame}
	\frametitle{Combinatorial Optimization}
	An old European map coloured with 5 colours (taking the background into account)
	\begin{figure}[h]
		\begin{center}
			\def\svgwidth{0.3\textwidth}
			\includepdftex{europe}
		\end{center}
	\end{figure}
	\begin{block}{Questions}
		\begin{itemize}[<+->]
			\item How many colour are needed at minimum?
			\item How to  formally model this problem?
			\item How to proceed to find a feasible colouring?
		\end{itemize}
	\end{block}
\end{frame}

%----------------------------------------------------
%----------------------------------------------------
\subsubsection{Linear Programming}

%----------------------------------------------------
\begin{frame}
	\frametitle{Linear Programming}
	\begin{align*}
		\textnormal{Maximize}      &  & z & = & c_1 x_1     & + & c_2 x_2     & + & \dots & + & c_n x_n                                              \\
		\textnormal{Subject}       &  &   &   & a_{1 1} x_1 & + & a_{1 2} x_2 & + & \dots & + & a_{1 n} x_n & \leqslant  b_1                   &     \\
		\nonumber \textnormal{to:} &  &   &   & a_{2 1} x_1 & + & a_{2 2} x_2 & + & \dots & + & a_{2 n} x_n & \leqslant  b_2                   &     \\
		\nonumber                  &  &   &   & \dots       &   &             &   & \dots &   & \dots       &                                  &   & \\
		\nonumber                  &  &   &   & a_{m 1} x_1 & + & a_{m 2} x_2 & + & \dots & + & a_{m n} x_n & \leqslant  b_m                   &     \\
		                           &  &   &   &             &   &             &   &       &   & x_j         & \geqslant  0\  (j = 1, \dots, n)       \\
		\nonumber
	\end{align*}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Formalizing the optimization version of the map colouring problem}
	\begin{eqnarray*}
		\textnormal{Minimize}  &   z & = \sum_{k = 1}^n{y_k}     \\
		\nonumber \textnormal{Subject to:} & &\\
		\sum_{k = 1}^n{x_{ik}}    & = &1\quad    i = 1, \dots, n  \\
		x_{ik} - y_k    & \leqslant&0\quad   i, k = 1, \dots, n  \\
		x_{ik} + x_{jk}   &\leqslant & 1\quad  \forall(i, j)\  \textnormal{have a common border}, \\
		\nonumber & & \ \  \quad  k = 1, \dots, n\\
		x_{ik}, y_k \  &\in &\{0, 1\}
	\end{eqnarray*}
\end{frame}

%----------------------------------------------------
%----------------------------------------------------
\subsubsection{A Small Glossary on Graphs and Networks}

%----------------------------------------------------

\begin{frame}
	\frametitle{Graph Colouring}
	\begin{itemize}[<+->]
		\item Switzerland and its neighbour countries that we want to colour
		\item Each country is symbolized by a disk, and a common border is symbolized by a line connecting the corresponding countries
		\item  The map colouring can be transformed into the colouring of the vertices of a graph
	\end{itemize}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{swiss_colouring}
		\end{center}
	\end{figure}

\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Graph, Vertex, Edge, Path}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{graph_node_edge_path_cycle}
		\end{center}
	\end{figure}
\end{frame}
%----------------------------------------------------
\begin{frame}
	\frametitle{Tree, Forest, Bipartite Graph, Clique}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{graph_tree_forest_bipartite_clique}
		\end{center}
	\end{figure}
\end{frame}
%----------------------------------------------------
%----------------------------------------------------
\subsection{Elements of Algorithmic Complexity and Complexity Theory}
\frame{\center \Large \thesection .\thesubsection \ \alert{\insertsubsection}}

%----------------------------------------------------
\subsubsection{Algorithmic Complexity}
%----------------------------------------------------

%----------------------------------------------------
%----------------------------------------------------
\subsubsection{Bachmann-Landau Notation}

\begin{frame}
	\frametitle{Empirical Computational Effort}
	Building a travelling salesman tour as a function of the number $n$ of cities
	\begin{figure}[h]
		\begin{center}
			\includepdftex{big_O_tsp_n_log_n}
		\end{center}
	\end{figure}
\end{frame}


%----------------------------------------------------
\begin{frame}
	\frametitle{Bachmann-Landau Notations}
	\begin{itemize}[<+->]
		\item Big O notation
		\begin{itemize}[<+->]
			\item{\definition{$f(n) \in O(g(n))$} if $\exists n_0 > 0,  \exists c >0$ such that $\forall n \geqslant n_0, f(n) \leqslant c \cdot g(n)$}
			\item{ \definition{$f(n) \in \Omega(g(n))$} if $\exists n_0 > 0,  \exists c >0$ such that$\forall n \geqslant n_0, f(n) \geqslant c \cdot g(x)$}
			\item{\definition{$f(n) \in \Theta(g(n))$} if $\exists n_0 > 0,  \exists c_2 > c_1 > 0$ such that$\forall n \geqslant n_0, c_1 \cdot g(n) \leqslant f(n) \leqslant c_2 \cdot g(n)$}
		\end{itemize}
		\item Little o notation
		\begin{itemize}[<+->]
			\item{\definition{$f(n) \in o(g(n))$} if $\lim_{n \to \infty}{\frac{g(n)}{f(n)}} > 0$}
			\item{ \definition{$f(n) \in \omega(g(n))$}  if $\lim_{n \to \infty}{\frac{f(n)}{g(n)}} > 0$}
			\item{\definition{$f(n) \sim g(n)$} if $\lim_{n \to \infty}{\frac{f(n)}{g(n)}} = 1$}
		\end{itemize}
	\end{itemize}

\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Functions commonly encountered in algorithmic complexity}
	\begin{itemize}[<+->]
		\item $O(1)$: constant.
		\item $O(\log n)$: logarithmic; the base is not provided since $O(\log_a n) = O(\log_b n)$.
		\item $O(n^c)$: fractional power, with $0 < c < 1$.
		\item $O(n)$: linear.
		\item $O(n \log n)$: linearithmic.
		\item $O(n^2)$: quadratic.
		\item $O(n^3)$: cubic.
		\item $O(n^c)$: polynomial, with $c  > 1$ constant.
		\item $O(n^{\log n})$: quasi-polynomial, super-polynomial, sub-exponential.
		\item $O(c^n)$: exponential, with $c > 1$ constant.
		\item $O(n!)$: factorial.
	\end{itemize}
\end{frame}

%----------------------------------------------------
\begin{frame}[shrink]
	\frametitle{Functions commonly encountered in algorithmic complexity}
	%	The horizontal axis indicates the size of the problem (with exponential growth) and the vertical axis gives the order of magnitude of the computation time (with iterated-exponential growth, from a nano second to the expected life of our universe)
	\begin{figure}[h]
		\begin{center}
			\includepdftex{complexity}
		\end{center}
	\end{figure}
\end{frame}



%----------------------------------------------------
%----------------------------------------------------
\subsubsection{Encoding Scheme, Language and Turing Machine}


\subsubsection{Basic Complexity Classes}

%----------------------------------------------------
\begin{frame}
	\frametitle{Deterministic Turing Machine}
	Schematic representation of a deterministic Turing machine, which allows  modelling and formalizing a computer
	\begin{figure}[h]
		\begin{center}

			\includepdftex{turing_machine}

		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Specification of a Deterministic Turing Machine}
	\begin{itemize}[<+->]
		\item A tape alphabet $\Gamma$  containing at least 
		\begin{itemize}
			\item $\Sigma$, the set of symbols that encodes a decision problem instance
			\item The special blank symbol $b$ not belonging to $\Sigma$
			\item Eventually other control symbols
		\end{itemize}
		\item A set of states $Q$, containing at least
		      \begin{itemize}
			      \item $q_0$ (the initial state)
			      \item $q_Y$ (the final state indicating that the answer to the instance is ``yes")
			      \item $q_N$ (the final state indicating that the answer is ``no")
		      \end{itemize}
		\item A transition function $\delta : Q\setminus \{q_Y, q_N\} \times \Gamma \quad \rightarrow \quad Q \times \Gamma \times \{-1, 1\}$.
	\end{itemize}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Example of a Turing Machine Program}
	\begin{itemize}[<+->]
		\item Tape alphabet: $\Gamma = \{0, 1, b\}$\\
		\item Input alphabet: $\Sigma = \{0, 1\}$\\
		\item Set of states: $Q = \{q_0, q_1, q_2, q_3, q_Y, q_N\}$\\
		\item Transition function $\delta$
		      \begin{table}[]
			      \begin{tabular}{c|ccc}
				            & \multicolumn{3}{c}{ Symbol $\sigma \in \Gamma$ on the tape}                                   \\
				      State & 0                                                           & 1              & $b$            \\
				      \hline
				      $q_0$ & $(q_0, 0, 1)$                                               & $(q_0, 1, 1)$  & $(q_1, b, -1)$ \\
				      $q_1$ & $(q_2, b, -1)$                                              & $(q_3, b, -1)$ & $(q_N, b, -1)$ \\
				      $q_2$ & $(q_Y, b, -1)$                                              & $(q_N, b, -1)$ & $(q_N, b, -1)$ \\
				      $q_3$ & $(q_N, b, -1)$                                              & $(q_N, b, -1)$ & $(q_N, b, -1)$ \\
			      \end{tabular}
		      \end{table}
	\end{itemize}
\end{frame}


%----------------------------------------------------
\begin{frame}
	\frametitle{Class $P$ of languages}
	\begin{itemize}[<+->]
		\item The machine $M$ \definition{accepts} $x \in \Sigma^*$ if and only if $M$ stops in the state $q_Y$
		\item The \definition{language recognized} by $M$ is the set of strings $x \in \Sigma^*$ such that $M$ accepts $x$
		\item An \definition{algorithm}\index{Algorithm!definition} is a program that stops for any string $x \in \Sigma^*$
		\item The \definition{computational time}\index{Computational time} of an algorithm is the number of steps performed by the machine before it stops
		\item The \definition{complexity}\index{Complexity} of a program $M$ is the \emph{largest} computational time $T_M(n)$ required by the machine to stop, whatever the string $x$ of length $n$ initially written on the tape is
		\item A deterministic Turing machine program is in \definition{polynomial time}\index{Polynomial} if there is a polynomial $p$ such that $T_M(n) \leqslant p(n)$
		\item The \definition{class $P$} of languages includes all the languages $L$ such that there is a program for deterministic Turing machine recognizing $L$ in polynomial time
	\end{itemize}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Non-deterministic Turing machine}
	\begin{itemize}[<+->]
		\item Schematic representation of a non-deterministic Turing machine
		\item This machine allows formalizing the  $NP$ class, but does not exist in the real world
	\end{itemize}
	\begin{figure}[h]
		\begin{center}
			\includepdftex{nd_turing_machine}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Class NP of languages}
	\begin{block}{Languages $L$ for which there exists a program $M$ for a non-deterministic Turing machine so that $M$ recognizes $L$ in \alert{polynomial} time}
		\begin{itemize}[<+->]
			\item The guessing module writes the solution of the problem into the negative index cells of the tape
			\item The program has just to verify that the solution is correct
			\item Informally the $NP$ class contains all problems for which a solution can be verified in polynomial time
		\end{itemize}
	\end{block}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Polynomial-Time Reduction}
	\begin{itemize}[<+->]
		\item Reduction of $Problem_1$ to $Problem_2$ in  time $T(n)$ where 
		\item If $T(n)$ is a polynomial and $Problem_1$ has a solution $\iff$ $Problem_1$ has a solution, then we have a \definition{polynomial-time reduction}
		\item The theory only requires to be able to carry out the operations represented with solid line arrows
	\end{itemize}
	\begin{figure}
		\begin{center}
			\includepdftex{polynomial_transform}
		\end{center}
	\end{figure}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Class NP-Complete}
	A problem $\pi$ belongs to the \definition{class NP-Complete} if $\pi$ belongs to $NP$ and every problem of $NP$ can be polynomially reduced to  $\pi$
	\begin{itemize}[<+->]
		\item If $\pi$ is NP-complete and $\pi$ can be solved in polynomial time, then $P = NP$
		\item If $\pi$ is NP-complete and $\pi$ does not belong to $P$, then $P\neq NP$
		\item If $\pi_1$ polynomially reduces to $\pi_2$ and $\pi_2$ polynomially reduces to $\pi_3$, then $\pi_1$ polynomially reduces to $\pi_3$
		\item If $\pi_1$ is NP-complete, $\pi_2$ belongs to $NP$ and  $\pi_1$ polynomially reduces to $\pi_2$, then $\pi_2$ is NP-complete
		\item (Cook) satisfiability is NP-complete; using the properties above, it is quite easy to show that other problems are NP-complete:
		      \begin{itemize}
			      \item Stable set
			      \item Graph colouring
			      \item Integer linear programming
			      \item Travelling salesman
			      \item etc.
		      \end{itemize}

	\end{itemize}
\end{frame}

%----------------------------------------------------
\begin{frame}
	\frametitle{Polynomial Reduction of Satisfiability to the Stable Set Problem}
	$(\bar{x} \lor y \lor \bar{z}) \land (x \lor \bar{y}) \land (y \lor z)$
	\begin{figure}[h]
		\begin{center}
			\includepdftex{satisfiability_to_stable}
		\end{center}
	\end{figure}
\end{frame}


%----------------------------------------------------
\begin{frame}
	\frametitle{Other Complexity Classes}
	\begin{itemize}[<+->]
		\item \definition{NP-Hard}\quad Extension of NP-complete to non-decision problems
		\begin{itemize}
			\item Optimization version of NP-complete problems
		\end{itemize}
		\item \definition{P-SPACE}\quad Can be solved with a memory limited by a polynomial
		\begin{itemize}
			\item Determine if a two-player game is fair
		\end{itemize}
		\item \definition{Class $L$}\quad Can be solved with an additional memory limited by a logarithmic of the data size
		\begin{itemize}
			\item Processing a database not fitting in RAM
		\end{itemize}
		\item \definition{Class $NC$}\quad Can be solved in polylogarithmic time on a machine including a poylnomial number of processors
		\begin{itemize}
			\item Sorting the elements of an array
		\end{itemize}
	\end{itemize}
\end{frame}

