Dans un graphe aléatoire, on cherche le plus de sommets possible sans qu’aucun soit relié à un autre. Tanya avance de proche en proche, bannit les sommets très connectés pour libérer leurs voisins, puis améliore son résultat par échanges. Voici un exemple, étape par étape.
Cette suite d’étapes vient d’une exécution réelle de l’algorithme (règles sûres et échanges désactivés pour garder l’exemple lisible). Les flèches du clavier font aussi avancer.
Tanya lance plusieurs essais indépendants (20 par défaut) et garde le meilleur. Chaque essai a quatre temps.
Le résultat est toujours un ensemble indépendant valide et maximal. Pour c < e, les règles sûres vident à elles seules le graphe et l’algorithme atteint i. Pour c > e, il reste des sommets de degré au moins 2 : c’est le bannissement et les échanges qui travaillent.
Graphe aléatoire de 100 sommets et 267 liaisons (c = 5), premier essai. Tanya choisit 44 sommets, soit l’optimum exact. Min-degré en trouve 41.
Le trait orange est le premier départ. Le sommet 18 a 11 liaisons : c’est le maximum, on le bannit. Son voisin 75 n’a plus qu’une liaison, il est approuvé et bloque 68. La chaîne repart des voisins de 68, bannit 67 puis 81, et approuve 8. Le sommet 67 est ensuite récupéré par la reprise, puisqu’il n’a plus de voisin choisi.
La chaîne ne se lance que 3 fois sur ce graphe, car les règles sûres font une grande partie du travail. Deux échanges 2-3 portent la sélection de 42 à 44 sommets.
Trois graphes (graines 1, 2 et 3), chacun avec environ 2 000 liaisons et 97 à 99 % des sommets dans la même composante connexe. Les valeurs sont le nombre de sommets sélectionnés.
| Méthode | Graphe 1 | Graphe 2 | Graphe 3 | Moyenne | An / n | Temps |
|---|---|---|---|---|---|---|
| min-degré | 461 | 474 | 468 | 467,7 | 0,468 | < 0,01 s |
| hybride | 469 | 477 | 468 | 471,3 | 0,471 | < 0,01 s |
| hybride + échanges 1-2 | 469 | 477 | 470 | 472,0 | 0,472 | 0,01 s |
| Tanya (20 essais) | 469 | 475 | 470 | 471,3 | 0,471 | 0,55 s |
| exact (60 s, non terminé) | 471 | 479 | 470 | 473,3 | 0,473 | 60 s |
| ILS (5 s) | 471 | 480 | 473 | 474,7 | 0,475 | 5,01 s |
L’exact (programmation linéaire en nombres entiers) a atteint sa limite de 60 secondes sur les trois graphes : son résultat est une borne basse de In, pas une valeur prouvée optimale. L’ILS, en 5 secondes, égale ou dépasse l’exact sur les trois graphes (il le dépasse sur deux). La meilleure valeur connue est donc celle de l’ILS, environ 0,475, et Tanya en est à environ 0,003.
Tanya passe devant min-degré et rejoint l’hybride en une demi-seconde, mais reste un peu sous l’ILS, qui défait des choix de façon répétée sur toute sa durée.
| Version | Graphe 1 | Graphe 2 | Graphe 3 | Moyenne | Temps |
|---|---|---|---|---|---|
| chaîne + règles sûres, sans reprise ni échanges | 413 | 422 | 409 | 414,7 | 0,19 s |
| + reprise des sommets libres | 456 | 464 | 460 | 460,0 | 0,21 s |
| + échanges 1-2 et 2-3 (1 essai) | 464 | 475 | 463 | 467,3 | 0,02 s |
| 20 essais | 469 | 475 | 472 | 472,0 | 0,47 s |
| 100 essais | 470 | 478 | 472 | 473,3 | 2,26 s |
La chaîne seule, sans reprise, est faible (environ 415). La reprise et les échanges font presque tout le reste. Passer de 20 à 100 essais ne gagne plus que 1,3 sommet en moyenne : les essais se ressemblent trop, il faut améliorer la construction plutôt que les répéter.
Tanya varie de 1 à 2 sommets selon la graine du hasard (les deux tableaux ont été tirés avec des graines différentes). Trois graphes seulement : ce sont des ordres de grandeur, pas une étude statistique.
Pour c < e, on a une formule exacte avec la fonction W de Lambert (W eW = c) :
Mesure avec la suppression de feuilles seule (règle « 0 ou 1 liaison »), à n = 100 000, qui est exacte dans ce régime :
| c | Mesuré | Formule |
|---|---|---|
| 0,5 | 0,8277 | 0,8272 |
| 1 | 0,7293 | 0,7280 |
| 2 | 0,6094 | 0,6080 |
| 2,5 | 0,5681 | 0,5672 |
Proche de e (à c = 2,7), il reste à n fini un noyau de sommets que cette règle ne traite pas, et la mesure s’écarte un peu de la formule (0,5499 contre 0,5531).
Pour c > e, il n’y a pas de formule simple. Les algorithmes gloutons classiques atteignent environ n·ln(c)/c sommets, alors que le maximum est d’environ 2n·ln(c)/c pour c grand. Combler cet écart avec un algorithme rapide est le sujet ouvert.
Ce sont des hypothèses, non testées à ce jour.