\documentclass[8pt]{beamer}
\usepackage[ansinew]{inputenc}
\usepackage{amssymb, color}
\usepackage{graphicx}
\usepackage{beamerthemesplit}
\usepackage[french]{babel}

\title{Le découpage des graphes, un aspect de l'informatique théorique}
\author{P. Pansu, Université Paris-Sud 11 et Ecole Normale Supérieure}
\date{\today}

\newtheorem{thm}{Théorème}
\newtheorem{lem}{Lemme}
\newtheorem{prop}[lem]{Proposition}
\newtheorem{cor}[lem]{Corollaire}
\newtheorem{defi}[lem]{Définition}
\newtheorem{rem}[lem]{Remarque}
\newtheorem{nota}[lem]{Notation}
\newtheorem{ques}[lem]{Question}
\newtheorem{obj}[lem]{Objectif}
\newtheorem{prob}[lem]{Problème}
\newtheorem{sol}[lem]{Solution}
\newtheorem{conc}[lem]{Conclusion}
\newtheorem{ex}[lem]{Exemple}
\newtheorem{exs}[lem]{Exemples}
\newtheorem{res}[lem]{Resultats}
\newtheorem{plan}[lem]{Plan de l'exposé}
\newtheorem{preuve}[lem]{Preuve}

\def\proof{\par\medskip\noindent {\bf Preuve}}
\def\qed{~q.e.d.}

\def\R{\mathbb{R}}
\def\texorpdfstring#1#2{#1}

\mode<presentation>{\usetheme{Warsaw}}

\begin{document}

\begin{frame}
\titlepage
\end{frame}

\section{Contagion}
\subsection{Réseaux d'ordinateurs}

\begin{frame}

Un virus se balade sur le réseau local de l'Institut Henri Poincaré. Déjà 5 machines infectées. On coupe les connexions qui les relient aux ordinateurs encore sains. \pause 
Il y en a 9.

\begin{center}
\includegraphics[width=2in]{reseau3.pdf}
\end{center}

\end{frame}

\begin{frame}

Un virus se balade sur le réseau local de l'Institut Henri Poincaré. Déjà 5 machines infectées. On coupe les connexions qui les relient aux ordinateurs encore sains. Il y en a 9.

\begin{center}
\includegraphics[width=2in]{reseau2.pdf}
\end{center}

Un réseau n'est rien d'autre qu'un graphe : ici, 9 sommets, 13 arêtes. L'infection consiste à colorier une partie des sommets. \pause 
La thérapie, à couper les arêtes bicolores. Ici, 9 arêtes coupées.

\end{frame}


\begin{frame}

Il a suffit de couper 9 arêtes. Est ce que cela aurait pu être pire ? Existe t'il des infections qui nécessitent une thérapie plus radicale ? \pause

\begin{ques}
Existe-t'il un coloriage donnant plus de 9 arêtes bicolores ?
\end{ques}

\begin{center}
\includegraphics[width=2in]{reseau4.pdf}
\end{center}


\end{frame}

\begin{frame}

Il a suffit de couper 9 arêtes. Est ce que cela aurait pu être pire ? Existe t'il des infections qui nécessitent une thérapie plus radicale ?

\begin{ques}
Existe-t'il un coloriage donnant plus de 9 arêtes bicolores ?
\end{ques}

\begin{center}
\includegraphics[width=2in]{reseau5.pdf}
\end{center}

Oui, 11 arêtes. Mais jamais davantage.
\end{frame}

\subsection{La coupe maximale}

\begin{frame}

\begin{defi}
Soit $G$ un graphe. On appelle coupe maximale$(G)$ le nombre maximal d'arêtes bicolores dans un coloriage de $G$.
\end{defi}

Le graphe étudié jusqu'à présent a une coupe maximale de 11.

Quelles sont les coupes maximales des graphes ci-dessous ?

\begin{center}
\includegraphics[width=1.5in]{reseau6.pdf}\hskip1cm\includegraphics[width=1.5in]{reseau7.pdf}
\end{center}


\end{frame}

\begin{frame}

\begin{defi}
Soit $G$ un graphe. On appelle coupe maximale$(G)$ le nombre maximal d'arêtes bicolores dans un coloriage de $G$.
\end{defi}

Le graphe étudié jusqu'à présent a une coupe maximale de 10.

Quels sont les coupes maximales des graphes ci-dessous ?

\begin{center}
\includegraphics[width=1.5in]{reseau5.pdf}\hskip1cm\includegraphics[width=1.5in]{reseau7.pdf}
\end{center}


\end{frame}

\begin{frame}

\begin{defi}
Soit $G$ un graphe. On appelle coupe maximale$(G)$ le nombre maximal d'arêtes bicolores dans un coloriage de $G$.
\end{defi}

Le graphe étudié jusqu'à présent a une coupe maximale de 10.

Quels sont les coupes maximales des graphes ci-dessous ?

\begin{center}
\includegraphics[width=1.5in]{reseau8.pdf}\hskip1cm\includegraphics[width=1.5in]{reseau7.pdf}
\end{center}


\end{frame}

\begin{frame}

\begin{defi}
Soit $G$ un graphe. On appelle coupe maximale$(G)$ le nombre maximal d'arêtes bicolores dans un coloriage de $G$.
\end{defi}

Le graphe étudié jusqu'à présent a une coupe maximale de 10.

Quels sont les coupes maximales des graphes ci-dessous ?

\begin{center}
\includegraphics[width=1.5in]{reseau8.pdf}\hskip1cm\includegraphics[width=1.5in]{reseau9.pdf}
\end{center}


\end{frame}

\subsection{Le problème MAX CUT}

\begin{frame}

\begin{prob}
MAX CUT : Ecrire un programme d'ordinateur qui, étant donnés un graphe $G$ à $n$ sommets, et un nombre entier $k$, décide si la coupe maximale de $G$ est $\geq k$ ou non.
\end{prob}\pause

\begin{sol}
Enumérer tous les coloriages, compter les arêtes bicolores. S'arrêter dès qu'un nombre $\geq k$ a été rencontré, ou aller jusqu'au bout et conclure que la coupe maximale de $G$ est $< k$.
\end{sol}\pause

\textbf{Analyse}: Il est possible qu'il faille $2^n$ opérations. Pour un graphe à $n=90$ sommets (réseau local de mon labo), ça fait plus de $10^{27}$ opérations. A une fréquence d'horloge de 1 GHz, ça prend 4 milliards d'années.\pause

$2^n$, c'est trop. Il faut trouver un programme qui accomplit la tâche en $n^d$ opérations. Par exemple, si $n=90$, $d=2$, $n^d =8100$ opérations et l'affaire de quelques microsecondes. \pause
\begin{defi}
Lorsque le temps d'éxécution est borné par $c\,n^d$, où $c$ et $d$ sont constants, on dit que le temps d'éxécution est {\em polynômial}.
\end{defi}

\end{frame}

\subsection{Problèmes P et NP}

\begin{frame}

\begin{defi}
Un problème est dit P s'il existe un programme d'ordinateur qui résoud le problème (répond oui ou non) en temps polynômial par rapport à la taille des données.
\end{defi}

Autrement dit, on se demande si le problème MAX CUT est P. La réponse à cette question est \textbf{inconnue}.\pause

\smallskip

Pour prouver que coupe maximale$(G)\geq k$, il suffit de dessiner un coloriage. Vérifier cette preuve, i.e. compter les arêtes bicolores, ne nécessite que $c\,n^2$ opérations.\pause

Plus généralement, j'appelle \emph{problème de recherche} un problème de la forme : existe t'il un objet qui satisfait telle condition ?

\begin{defi}
La classe NP est la classe des problèmes de recherche pour lesquels vérifier si un objet est bien une solution se fait en temps polynômial en la taille de l'objet.
\end{defi}\pause

Le problème MAX CUT est NP. Les objets sont les coloriages. La condition est nombre d'arêtes coupées $\geq k$.

Le problème de trouver une démonstration d'un théorème mathématique est NP. En effet, vérifier qu'une preuve convenablement rédigée est correcte peut se faire en temps polynômial en la longueur de la preuve.

\end{frame}

\subsection{NP-complétude}

\begin{frame}

On ignore si tous les problèmes NP sont P. C'est la fameuse conjecture P$\not=$NP, qui remonte à Kurt Gödel (lettre à John von Neumann, 1956), mise à prix 1000000\$.\pause

\begin{defi}
Un problème est dit {\em NP-complet} s'il est NP, et si tout problème NP s'y ramène en temps polynômial.
\end{defi}

Si l'un d'entre eux est P, alors P$=$NP. Si l'un d'entre eux n'est pas P, alors P$\not=$NP.\pause

\begin{thm}[Cook, Levine (1971), Karp (1972)]
MAX CUT est NP-complet.
\end{thm}

Autrement dit, on ignore si MAX CUT est P, mais s'il l'est, \emph{cela aurait des conséquences de la plus haute importance. C'est-à-dire, cela montrerait, en dépit de l'incomplétude, que le travail intellectuel des mathématiciens, dans le cas des problèmes de décision, pourrait être entièrement remplacé par les machines... Cela me semble néanmoins du domaine du possible} (Gödel).

\end{frame}

\section{Problème MAX CUT approché}

\begin{frame}

Puisqu'on ne peut problement pas résoudre exactement le problème MAX CUT, on tente de le résoudre de façon approchée.\pause

\begin{defi}
Soit $\alpha<1$. Une {\em résolution $\alpha$-approchée} de MAX CUT, c'est un programme d'ordinateur qui, étant donné un graphe $G$ à $n$ sommets, trouve en un temps polynômial en $n$, un coloriage dont le nombre d'arêtes bicolores est $\geq \alpha\times$coupe maximale$(G)$. Ce programme a le droit d'effectuer des tirages au hasard. On demande dans ce cas que le score annoncé soit obtenu avec probabilité $\geq \frac{1}{2}$.
\end{defi}\pause

\begin{ex}
Coloriage aléatoire. On tire indépendamment au hasard la couleur de chaque sommet.
\end{ex}\pause
\textbf{Analyse}: Chaque arête a une chance sur deux d'être bicolore. L'espérance du nombre d'arêtes bicolores vaut $\frac{1}{2}\times$nombre d'arêtes $\geq \frac{1}{2}\times$coupe maximale$(G)$. Par symétrie, avec probabilité $\geq \frac{1}{2}$, 
\begin{center}
nombre d'arêtes bicolores $\geq \frac{1}{2}$coupe maximale$(G)$.
\end{center}
Donc il s'agit d'une résolution $\frac{1}{2}$-approchée de MAX CUT.

\end{frame}

\subsection{La méthode de Goemans et Williamson}

\begin{frame}

\begin{thm}[Goemans-Williamson 1995]
Le problème MAX CUT possède une résolution $0.878...$-approchée.
\end{thm}\pause

On explique la méthode dans le cas d'un graphe à $3$ sommets et $3$ arêtes. 

On dessine le graphe sur une sphère. Les sommets deviennent des vecteurs $v_1$, $v_2$ et $v_3$. On les dispose de sorte à rendre la quantité suivante la plus grande possible
\begin{eqnarray*}
\textrm{SDP}=\frac{1}{2}(1-v_1 \cdot v_2)+\frac{1}{2}(1-v_2 \cdot v_3)+\frac{1}{2}(1-v_3 \cdot v_1).
\end{eqnarray*}\pause
On admet qu'il y a un algorithme polynômial pour le faire (basé sur l'algèbre linéaire). L'idée est qu'à tout coloriage correspond une disposition particulière des vecteurs (superposés sur deux points diamétralement opposés), pour laquelle SDP est le nombre d'arêtes bicolores. En particulier, $\max$ SDP $\geq$ coupe maximale.\pause

Inversement, on associe un coloriage à la disposition optimale comme suit : on coupe le graphe en deux au moyen d'un plan tiré au hasard. 

\begin{center}
\includegraphics[width=1in]{gw.pdf}
\end{center}
\end{frame}

\begin{frame}

La probabilité que l'arête $v_i v_j$ soit coupée (bicolore) vaut $\frac{1}{\pi}\arccos(v_i \cdot v_j)$. L'espérance du nombre d'arêtes bicolores est
\begin{eqnarray*}
E=\frac{1}{\pi}\arccos(v_1 \cdot v_2)+\frac{1}{\pi}\arccos(v_2 \cdot v_3)+\frac{1}{\pi}\arccos(v_3 \cdot v_1).
\end{eqnarray*}\pause
A comparer à
\begin{eqnarray*}
\textrm{SDP}=\frac{1}{2}(1-v_1 \cdot v_2)+\frac{1}{2}(1-v_2 \cdot v_3)+\frac{1}{2}(1-v_3 \cdot v_1).
\end{eqnarray*}\pause

On constate que 
$E\geq I\times\max SDP\geq I\times$coupe maximale, où
\begin{eqnarray*}
I=\min_{-1\leq x\leq 1}\frac{\frac{1}{\pi}\arccos(x)}{\frac{1}{2}(1-x)}=\min_{0\leq t\leq \pi}\frac{2t}{\pi(1-\cos t)}. 
\end{eqnarray*}
Donc la méthode de Goemans-Williamson est une $I$-approximation de MAX CUT.

\end{frame}


\begin{frame}

Comment calculer $I$ ? On étudie la fonction $t\mapsto f(t)=\frac{\pi(1-\cos t)}{2t}$ sur l'intervalle $[0,\pi]$.

$$f'(t)=\frac{\pi}{2}\frac{t\sin t -(1-\cos t)}{t^2}$$\pause

$$g(t)=t\sin t -(1-\cos t)$$\pause

$$g'(t)=\sin t +t\cos t-\sin t =t\cos t$$\pause

\begin{center}
\begin{tabular}{|c|ccccc|}
\hline
$t$   & $0$ && $\pi/2$ && $\pi$ \\
\hline
$g'(t)$   & $0$  & $+$ & $0$ & $-$ &\\
\hline
$g(t)$   &  $0$ & $\nearrow$ & $g(\pi/2)$ & $\searrow$ & $-2$ \\
\hline
\end{tabular}
\end{center}\pause

\begin{center}
\begin{tabular}{|c|ccccc|}
\hline
$t$   & $0$ && $a$ && $\pi$ \\
\hline
$f'(t)$   & $0$  & $+$ & $0$ & $-$ &\\
\hline
$f(t)$   &  $0$ & $\nearrow$ & $f(a)$ & $\searrow$ & $1$ \\
\hline
\end{tabular}
\end{center}\pause

Par approximation successives, on trouve $a=2.331122370414423...$ puis $I=1/f(a)=0.8785672057848516...$.
\end{frame}


\subsection{Le nombre 0.878... est-il le seuil optimal d'approximabilité ?}


\begin{frame}

\begin{rem}[U. Feige, G. Schechtman 2002]
Il existe des graphes pour lesquels la méthode donne une coupe arbitrairement proche de $I\times$coupe maximale.
\end{rem}\pause

\begin{thm}[S. Khot, G. Kindler, E. Mossel, R. O'Donnell 2005]
Sous une hypothèse un peu plus forte que P$\not=$NP, $I=0.8785672057848516...$ est le seuil optimal d'approximabilité pour MAX CUT. Autrement dit, si $\alpha>I$, il n'existe pas de résolution $\alpha$-approchée de MAX CUT.
\end{thm}\pause

\medskip

La preuve est l'aboutissement d'idées qui remontent à Gödel (vérification de preuves, vérification probabiliste de preuves) et fait intervenir de l'analyse originale (isopérimétrie dans le cube discret).

\medskip

Pour en savoir davantage, utiliser les mots clés suivants : semi-definite programming, polynomial time approximation schemes, PCP theorem, Unique Games Conjecture.


\end{frame}

\end{document}

% 0.8785672057848516
% 2.331122370414423