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.

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. La thérapie, à couper les arêtes bicolores. Ici, 9 arêtes coupées.

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 ?

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

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

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

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.

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},\]

où

\[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.

Prenez la peine de le démontrer !