Probleme – La coupe maximale : le hasard, puis mieux

1. L'analyse tient en deux lignes. Une arête $\{u,v\}$ est coupée si et seulement si $u$ et $v$ tombent de part et d'autre, ce qui arrive dans deux cas sur quatre : la probabilité vaut $1/2$. Par linéarité de l'espérance, sur $m$ arêtes,

$$\mathbb{E}[\text{valeur de la coupe}]=\frac{m}{2}\ge \frac{OPT}{2},$$

la dernière inégalité venant de ce qu'aucune coupe ne peut dépasser le nombre total d'arêtes. C'est exactement l'argument de MAX2SAT, transposé — et comme lui, il n'exige aucune indépendance entre les arêtes, alors qu'elles partagent des sommets.

2. La borne est atteinte. Il suffit d'un graphe où l'optimum coupe toutes les arêtes, c'est-à-dire d'un graphe biparti. Sur $K_{3,3}$ — six sommets, neuf arêtes —, la coupe maximale vaut $9$ tandis que l'espérance vaut $4,5$ : le rapport est exactement $1/2$.

Vérification sur $4000$ graphes aléatoires : le rapport exact $\mathbb{E}[ALG]/OPT$ ne descend jamais sous $0,5000$, et vaut exactement $1/2$ dans $1328$ cas — précisément ceux où le graphe est biparti.

3. La recherche locale. On part d'une coupe quelconque, et l'on fait basculer tout sommet qui a strictement plus de voisins de son côté que de l'autre.

(* Coupe de valeur au moins m/2, DETERMINISTE.
   Entrees : g.(u) = liste des voisins de u, graphe non oriente.
   Sortie  : cote.(u) = true ou false, la partition.
   Complexite : O(m^2) au pire -- au plus m basculements, chacun en O(m). *)
let coupe_locale g =
  let n = Array.length g in
  let cote = Array.make n true in                 (* tout le monde du meme cote *)
  let bouge = ref true in
  (* VARIANT : la valeur de la coupe, entiere, majoree par m, et qui augmente
     d'au moins 1 a chaque basculement. *)
  while !bouge do
    bouge := false;
    for u = 0 to n - 1 do
      let memes = List.fold_left
        (fun acc v -> if cote.(v) = cote.(u) then acc + 1 else acc) 0 g.(u) in
      let autres = List.length g.(u) - memes in
      if memes > autres then begin                (* on gagne memes - autres *)
        cote.(u) <- not cote.(u);
        bouge := true
      end
    done
  done;
  cote

Terminaison. Le variant est la valeur de la coupe elle-même. Faire basculer $u$ fait entrer dans la coupe les memes arêtes de son côté et en sortir les autres : la valeur varie de $\text{memes}-\text{autres}\ge 1$, puisqu'on ne bascule que si $\text{memes}>\text{autres}$ et que ce sont des entiers. La valeur est un entier strictement croissant majoré par $m$ : il y a au plus $m$ basculements. C'est un variant qui croît vers un maximum — l'exact miroir du variant décroissant habituel, et il est tout aussi rigoureux.

Garantie. À l'arrêt, tout sommet $u$ vérifie $\text{memes}(u)\le \text{autres}(u)$, donc au moins la moitié de ses arêtes sont coupées. En sommant sur tous les sommets, chaque arête étant comptée deux fois :

$$2\times \text{valeur de la coupe}=\sum _u\text{autres}(u)\ge \sum _u\frac{\mathrm{deg}(u)}{2}=m,$$

d'où valeur $\ge m/2\ge OPT/2$. La même garantie que le tirage aléatoire, sans aucun tirage.

4. Les mesures, sur $4000$ graphes aléatoires de $3$ à $8$ sommets, l'optimum étant calculé par énumération des $2^n$ partitions :

Le nombre de basculements n'a jamais dépassé $8$ sur ces instances, très en deçà de la borne $m$.

Ce que le problème enseigne. La méthode probabiliste a d'abord servi à prouver qu'il existe une coupe de valeur $\ge m/2$ — pur argument d'existence. La recherche locale la trouve, sans hasard, et sa preuve de garantie est une conséquence de sa condition d'arrêt. C'est le même mouvement qu'au problème « MAX2SAT : du hasard au déterminisme » : le hasard découvre le résultat, un algorithme déterministe le réalise.

Et une mise en garde, pour ne pas surestimer la recherche locale : elle rend un optimum local, pas global. Sur les instances mesurées, elle atteint $0,571$ au pire, mais rien ne garantit mieux que $1/2$ — et l'algorithme le plus fort connu pour la coupe maximale, celui de Goemans et Williamson, n'atteint $0,878$ qu'au prix d'une relaxation par programmation semi-définie, très au-delà du programme.