Le découpage des graphes

Un aspect de l’informatique théorique

Piste noire Le 10 novembre 2011  - Ecrit par  Pierre Pansu Voir les commentaires

Cet article a été écrit en partenariat avec Le Séminaire Bourbaki

Cet article est une introduction « élémentaire » à un exposé que le même auteur donnera le 19 novembre 2011 dans le cadre du Séminaire Bourbaki à l’Institut Henri Poincaré, rue Pierre et Marie Curie, Paris 5 ème.

Un virus se balade sur le réseau local de mon établissement. Seule thérapie : couper les connexions entre ordinateurs sains et ordinateurs infectés. Combien y a t-il de connexions à couper, dans le pire des cas ? Le calcul exact de ce nombre pour de grands réseaux est difficile. On sait le faire à 87.85672057848516% près, mais pas à 87.85672057848517% près. On dirait une curiosité mathématique. En fait, les problèmes de découpage de graphes sont typiques en informatique, à la fois pour les applications pratiques et sous l’angle théorique.

Contagion

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

JPEG - 103.2 ko

Un réseau n’est rien d’autre qu’un graphe : ici, 9 sommets, 13 arêtes.

JPEG - 59.5 ko

L’infection consiste à colorier une partie des sommets. La thérapie, à couper les arêtes bicolores. Ici, 9 arêtes coupées.

JPEG - 66.4 ko

Il a suffi 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 ?

Question. Existe-t-il un coloriage donnant plus de 9 arêtes bicolores ?

JPEG - 64.5 ko

Oui, 11 arêtes. Mais jamais davantage.

La coupe maximale

On appelle coupe maximale d’un graphe $G$ le nombre maximal d’arêtes bicolores dans un coloriage de $G$.

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

Question : quelles sont les coupes maximales des graphes ci-dessous (cliquer pour agrandir) ?

JPEG - 63.2 ko
JPEG - 62.9 ko

Réponse à la fin de l’article.

Le problème MAX CUT

Le problème MAX CUT consiste à écrire un programme d’ordinateur qui calcule la coupe maximale d’un graphe. Techniquement, étant donnés un graphe $G$ à $n$ sommets, et un nombre entier $k$, l’ordinateur doit dire si la coupe maximale de $G$ est supérieure à $k$ ou non.

Voici une solution simple : Enumérer tous les coloriages, compter les arêtes bicolores. S’arrêter dès qu’un nombre $> k$ a été rencontré, ou aller jusqu’au bout et conclure que la coupe maximale de $G$ est $< k$.

Qu’en pensez-vous ? Ce programme risque de prendre pas mal de temps. Il est possible que le coloriage optimal soit le dernier. Dans ce cas, il faut accomplir au moins $2^n$ opérations. Pour un graphe à $n=90$ sommets (réseau local de mon labo), cela fait plus de $10^{27}$ opérations. A une fréquence d’horloge de 1 GHz, cela prend 4 milliards d’années.

$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 est l’affaire de quelques microsecondes. Autrement dit, une suite géométrique ($2^n$) croît incroyablement plus vite qu’une suite quadratique ($n^2$) ou plus généralement polynômiale (inférieure à $c n^d$ où $c$ et $d$ ne dépendent pas de $n$). Il est donc important de se cantonner aux programmes dont le temps d’éxécution est polynômial

Problèmes P et NP

Lorsqu’il existe un programme d’ordinateur qui résoud un problème donné en temps polynômial par rapport à la taille des données, on dit que le problème appartient à la classe $P$.

Est-ce que le problème MAX CUT appartient à la classe $P$ ? La réponse à cette question est inconnue.

Pour prouver que coupe maximale($G$) $> 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, où $c$ est une constante.

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

Les 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 forment la classe $NP$.

Par exemple, le problème MAX CUT est $NP$. Les objets sont les coloriages. La condition est nombre d’arêtes coupées $> k$.

Le problème de trouver une démonstration d’un théorème mathématique appartient à la classe $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.

NP-complétude

On ignore si tous les problèmes $NP$ sont $P$. C’est la fameuse conjecture $P=NP$, qui remonte à Kurt Gödel (lettre à John von Neumann, 1956), mise à prix 1000000 dollars (Gödel est un logicien célèbre pour avoir démontré les limites du raisonnement mathématique, von Neumann le premier théoricien de l’informatique et le fondateur de la théorie des jeux).

On dit qu’un problème est $NP$-complet s’il est $NP$, et si tout problème $NP$ s’y ramène en temps polynômial.

Si l’un de ces problèmes est $P$, alors $P=NP$. Si l’un d’entre eux n’est pas $P$, alors $P$ est distinct de $NP$.

Théorème : [Cook, Levine (1971), Karp (1972)]

MAX CUT est NP-complet.

Autrement dit, on ignore si MAX CUT est $P$, mais s’il l’est, 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).

Problème MAX CUT approché

Puisqu’on ne peut probablement pas résoudre exactement le problème MAX CUT, on tente de le résoudre de façon approchée.

Soit $a<1$. Une résolution $a$-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 $> a$ fois 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é $>1/2$.

Voici une second tentative de résolution de MAX CUT : le coloriage aléatoire. On tire indépendamment au hasard la couleur de chaque sommet. Il y a peu de chances d’atteindre ainsi la coupe maximale. En revanche, on en obtient une assez bonne approximation.

En effet, chaque arête a une chance sur deux d’être bicolore. L’espérance du nombre d’arêtes bicolores vaut la moitié du nombre d’arêtes, qui est plus grand que la moitié de coupe maximale($G$). Par symétrie, avec probabilité $>1/2$,

nombre d’arêtes bicolores $> 1/2$ coupe maximale($G$).

Donc le coloriage aléatoire fournit une résolution $1/2$-approchée de MAX CUT.

La méthode de Goemans et Williamson

Théorème : [Goemans-Williamson 1995]

Le problème MAX CUT possède une résolution 0.878...-approchée.

On explique la méthode dans le cas d’un graphe à 3 sommets et 3 arêtes. Elle consiste à substituer aux grandeurs combinatoires des grandeurs géométriques (ou algébriques) plus accessibles au calcul.

L’idée (pas évidente du tout) de Michel Goemans et David Williamson consiste à dessiner le graphe sur une sphère de rayon $1$ en espaçant les sommets au maximum. Les sommets deviennent des vecteurs $v_1$, $v_2$ et $v_3$. On dispose les vecteurs de façon à rendre la somme des carrés des distances

\[SDP = \frac{1}{4} |v_1 - v_2|^2 + \frac{1}{4} |v_2 - v_3|^2 + \frac{1}{4} |v_3 - v_1|^2 \]

la plus grande possible. On admet qu’il y a un algorithme polynômial pour trouver la configuration optimale sur la sphère (basé sur l’algèbre linéaire).

On pense à cette configuration comme à un analogue géométrique d’un coloriage. En effet, un coloriage consiste à choisir pour chaque sommet une couleur, codée par l’un des nombres $-1$ et $1$ ($1$ pour le rouge, $-1$ pour le noir). Si $x_1$, $x_2$ et $x_3$ représentent les couleurs des 3 sommets, le nombre d’arêtes bicolores vaut

\[OBJ = \frac{1}{2} (1-x_1 x_2) + \frac{1}{2} (1-x_2 x_3) + \frac{1}{2} (1-x_3 x_1).\]

En développant la distance au carré au moyen du produit scalaire cher aux physiciens (il est positif si $v_1$ et $v_2$ forment un angle aigu, négatif si l’angle est obtus),

\[|v_1 - v_2|^2 = |v_1|^2 -2 v_1 . v_2 +|v_2|^2 = 2 - 2 v_1 . v_2 ,\]

il vient

\[SDP = \frac{1}{2} (1-v_1 . v_2) + \frac{1}{2} (1-v_2 . v_3) + \frac{1}{2} (1-v_3 . v_1).\]

On voit que chaque produit scalaire $v_1 . v_2$ remplace le produit usuel $x_1 x_2$ qui vaut $1$ si $v_1$ et $v_2$ sont de la même couleur, $-1$ s’ils sont de couleurs différentes. On peut penser à $x_1 ,x_2 , x_3$ comme à une disposition particulière des vecteurs, superposés sur deux points diamétralement opposés. Pour cette configuration, $SDP=OBJ$ est le nombre d’arêtes bicolores. En particulier, $max SDP \geq$ coupe maximale.

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

JPEG - 65.3 ko

Démonstration

La probabilité que l’arête $v_i v_j$ soit coupée (bicolore) vaut $\frac{1}{\pi} \arccos(v_i . v_j)$.

JPEG - 18.1 ko

En effet, un plan tiré uniformément au hasard coupe le plan contenant $v_1$ et $v_2$ suivant une droite tirée uniformément au hasard. Le plan coupe l’arête si et seulement si la droite coupe le secteur, d’angle $\theta$, délimité par $v_1$ et $v_2$ sur le cercle unité. Ceci se produit avec probabilité $\frac{\theta}{\pi} =\frac{1}{\pi} \arccos(v_1 . v_2)$.

Le nombre d’arêtes bicolores est une somme de variables aléatoires, une par arête, qui vaut $1$ si l’arête est coupée, $0$ sinon.

On utilise le fait que l’espérance d’une somme est la somme des espérances. L’espérance du nombre d’arêtes bicolores est

\[E = \frac{1}{\pi} \arccos(v_1 . v_2) + \frac{1}{\pi} \arccos(v_2 . v_3) + \frac{1}{\pi} \arccos(v_3 . v_1).\]

A comparer à

\[{SDP} = \frac{1}{2} (1-v_1 . v_2) + \frac{1}{2} (1-v_2 . v_3) + \frac{1}{2} (1-v_3 . v_1).\]

On constate que

\[E \geq I\,\,\, max SDP > I\,\,\, \rm{coupe \,\,\,\, maximale},\]

\[I=\min_{-1< x< 1} \frac{\frac{1}{\pi} \arccos(x)}{\frac{1}{2}(1-x)}=\min_{0< t< \pi} \frac{2t}{\pi(1-\cos t)}. \]

Donc la méthode de Goemans-Williamson est une I-approximation de MAX CUT.

Comment calculer I ? On étudie la fonction $t \mapsto f(t)=\pi\frac{1-\cos t}{2t} $ sur l’intervalle $[0,\pi]$.
On calcule
\[f'(t)=\frac{\pi}{2} \frac{t \sin t -(1-\cos t)}{t^2}.\]
On introduit
\[g(t)=t \sin t -(1-\cos t),\]
et on calcule
\[g'(t)=\sin t +t \cos t-\sin t =t \cos t,\]
dont le signe est facile à déterminer.
Du tableau de variations obtenu, il ressort que $f$ atteint un unique maximum $m$ entre $\pi/2$ et $\pi$. Par approximation successives, on trouve $m=2.331122370414423$... puis $I=1/f(m)=0.8785672057848516....$

Le nombre 0.878... est-il le seuil optimal d’approximabilité ?

Actuellement, on n’en est pas sûr. On dispose seulement d’indications encourageantes.

1. En 2002, Uriel Feige et Gideon Schechtman ont vérifié qu’il existe des graphes pour lesquels la méthode donne une coupe arbitrairement proche de $I$ fois coupe maximale.

2. En 2005, Subhash Khot, Guy Kindler, Elchanan Mossel et Ryan O’Donnell on prouvé que, 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 $a>I$, il n’existe pas de résolution $a$-approchée de MAX CUT.

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).

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

Conclusion

Le problème MAX CUT a été utilisé ici pour illustrer des progrès récents de l’algorithmique et de la théorie de la complexité. La méthode inaugurée par Goemans et Williamson a connu un succès foudroyant. Pour de nombreux problèmes combinatoires, un détour par l’algèbre linéaire (produits scalaires...) permet de trouver des solutions algorithmiques approchées. Depuis peu, on se rend compte que, dans bien des cas, cette méthode donne probablement la meilleure approximation théoriquement possible (sous l’hypothèse que $P$ est distinct de $NP$). C’était inespéré. Démontrer cette dernière affirmation (difficulté d’approximation) requiert pour chaque problème des développements mathématiques nouveaux et assez avancés. Voila pour la théorie. Sur le plan pratique, il est vraisemblable que les idées qui ont fait leurs preuves en théorie fassent progresser la recherche d’algorithmes d’usage industriel. Cela nécessite un gros travail d’ingéniérie qui n’a pas encore porté tous ses fruits.

Solution de la devinette

La coupe maximale vaut 12 dans les deux cas.

JPEG - 68.4 ko
JPEG - 69.2 ko

Prenez la peine de le démontrer !

Post-scriptum :

La rédaction d’Images des maths, ainsi que l’auteur, remercient pour leur relecture attentive,
les relecteurs dont le pseudonyme est le suivant : Michele Triestino, Claire Wenandy et Xavier Caruso .

Article édité par Étienne Ghys

Partager cet article

Pour citer cet article :

Pierre Pansu — «Le découpage des graphes» — Images des Mathématiques, CNRS, 2011

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM