Tanya : un glouton en chaîne pour l’ensemble indépendant

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.

Un exemple pas à pas sur 12 sommets

  • en jeu (le petit nombre est son nombre de liaisons)
  • approuvé
  • banni
  • bloqué
  • sommet regardé
  • candidat

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.

Le problème en bref

Graphe aléatoire G(n, c/n)
n sommets, chaque liaison étant présente avec probabilité c/n. Le nombre c est le degré moyen.
Ensemble indépendant
Un ensemble de sommets où aucun n’est relié à un autre de l’ensemble.
In et i
In est la taille maximale d’un ensemble indépendant. La proportion In / n tend vers une limite i, qui ne dépend que de c.
An
La taille de l’ensemble que trouve un algorithme. On a toujours An ≤ In, et on mesure la qualité par l’écart i − An / n.
Le seuil c = e ≈ 2,718
Pour c < e, les règles simples (prendre un sommet qui a 0 ou 1 liaison) suffisent à résoudre le graphe. Au-delà, les algorithmes simples restent en dessous de i.

L’algorithme en mots

Tanya lance plusieurs essais indépendants (20 par défaut) et garde le meilleur. Chaque essai a quatre temps.

  1. Règles sûres, appliquées au début puis après chaque pas de la chaîne. Elles ne font jamais perdre l’optimum :
    • un sommet à 0 ou 1 liaison est pris (il entre dans la sélection, ses voisins sortent du jeu) ;
    • un sommet à 2 liaisons dont les deux voisins sont reliés (triangle) est pris ;
    • domination : si tous les voisins d’un sommet v sont aussi voisins d’un voisin u de v (v et u compris), on bannit u.
  2. La chaîne.
    1. On part d’un sommet v de degré maximal (égalités tranchées par numéro au premier essai, au hasard ensuite). Ses voisins sont les candidats, et v est le sommet à bannir.
    2. Parmi les candidats, on garde w, celui qui a le moins de liaisons.
    3. On bannit le sommet à bannir : il sort du jeu sans être choisi, et ses voisins perdent une liaison.
    4. Si w a alors moins de 2 liaisons, il est approuvé : il entre dans la sélection et son éventuel voisin restant est bloqué. La chaîne repart des voisins encore en jeu de ce sommet bloqué, sans nouveau bannissement.
    5. Sinon, w devient le sommet courant : ses voisins sont les nouveaux candidats et c’est lui qu’on bannira au pas suivant.
    6. Sans candidat, on repart d’un autre sommet de degré maximal. Un sommet isolé est approuvé directement.
  3. Reprise. Certains sommets bannis n’ont finalement aucun voisin choisi. On les ajoute, ce qui rend la sélection maximale.
  4. Échanges (c’est ici que l’algorithme revient sur des choix) :
    • échange 1-2 : on retire un sommet choisi pour en ajouter deux libres, non reliés entre eux ;
    • échange 2-3 : un sommet non choisi touche exactement deux sommets choisis a et b. On retire a et b, et on ajoute trois sommets non reliés entre eux, pris parmi ceux qui ne touchaient que a ou b.
    On répète jusqu’à ce qu’aucun échange ne marche.

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.

Sur 100 sommets

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.

Graphe de 100 sommets après TanyaSommets choisis par la chaîne, ajoutés ensuite, bannis ou bloqués, avec le premier trajet de la chaîne en orange.18756867818

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.

Résultats à n = 1000 et c = 4

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éthodeGraphe 1Graphe 2Graphe 3MoyenneAn / nTemps
min-degré461474468467,70,468< 0,01 s
hybride469477468471,30,471< 0,01 s
hybride + échanges 1-2469477470472,00,4720,01 s
Tanya (20 essais)469475470471,30,4710,55 s
exact (60 s, non terminé)471479470473,30,47360 s
ILS (5 s)471480473474,70,4755,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.

Ce que chaque étape apporte

VersionGraphe 1Graphe 2Graphe 3MoyenneTemps
chaîne + règles sûres, sans reprise ni échanges413422409414,70,19 s
+ reprise des sommets libres456464460460,00,21 s
+ échanges 1-2 et 2-3 (1 essai)464475463467,30,02 s
20 essais469475472472,00,47 s
100 essais470478472473,32,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.

Ce que l’on sait de i(c)

Pour c < e, on a une formule exacte avec la fonction W de Lambert (W eW = c) :

i(c) = (2·W(c) + W(c)²) / (2c)

Mesure avec la suppression de feuilles seule (règle « 0 ou 1 liaison »), à n = 100 000, qui est exacte dans ce régime :

cMesuréFormule
0,50,82770,8272
10,72930,7280
20,60940,6080
2,50,56810,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.

Pistes d’amélioration

Ce sont des hypothèses, non testées à ce jour.

  1. Repliement des sommets de degré 2. Si v a deux voisins u et w non reliés, on fusionne les trois en un seul sommet, et la solution gagne un sommet au dépliage. C’est la règle exacte la plus forte après « 0 ou 1 liaison ».
  2. Échanges 1-1 sur plateau. Permuter un sommet choisi avec un voisin non choisi sans changer la taille, pour ouvrir de nouveaux échanges 1-2.
  3. Meilleur arbitrage des égalités. Préférer, à degré égal, le voisin dont les voisins sont les plus connectés.
  4. Départs plus variés. Choisir le sommet de départ au hasard parmi les sommets de degré presque maximal.