Algorithme de Wigderson

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

L'algorithme de Wigderson est un algorithme de coloration de graphe. C'est un algorithme de complexité en temps polynomiale, qui colore avec couleurs les graphes 3-coloriables. Il est dû à Avi Wigderson.

Description[modifier | modifier le code]

Cet algorithme s'effectue sur des graphes qu'on sait 3-coloriables. Soit un tel graphe. On note le nombre de sommets de

  1. On prend comme couleur initiale
  2. Pour tout non déjà colorié et avec au moins voisins non coloriés : on considère le sous graphe induit par l'ensemble des voisins de pas encore coloriés, et on le 2-colorie avec les couleurs et On ajoute à le nombre de couleurs utilisées.
  3. Avec l'algorithme glouton, on colorie le reste des sommets avec des couleurs plus grandes que

La complexité de l'algorithme de Wigderson est polynomiale en et détermine un coloriage de qui utilise couleurs.

Correction de l'algorithme de Wigderson[modifier | modifier le code]

L'algorithme de Wigderson renvoie bien un coloriage, car l'algorithme glouton et l'algorithme de 2-coloriage sont corrects, et que les sous-graphes considérés dans l'algorithme sont coloriés avec des ensembles de couleur disjoints.

Si on note le nombre de sommets traités durant le point 2, alors l'algorithme colorie au moins sommets. On a donc :

, i.e .

Ainsi le nombre de couleurs utilisées dans le point 2 est d'au plus . Ensuite, le degré du sous-graphe induit par les sommets non coloriés à la fin du point 2 est inférieur ou égal à . L'algorithme glouton utilise donc au plus couleurs pour colorier le reste des sommets. Ainsi, le nombre de couleurs utilisées est d'au plus , il est donc en .

Exemple[modifier | modifier le code]

Le graphe suivant est 3-coloriable :

Graphe 3-coloriable

Application de l'étape 2[modifier | modifier le code]

Le sommet a 4 voisins non coloriés : on les 2-colorie, puis on fait de même pour les 4 voisins non coloriés du sommet .

Après ces opérations, il n'y a plus de sommet non colorié avec au moins voisins non coloriés.

Étape 2 de l'algorithme de Wigderson

Application de l'étape 3[modifier | modifier le code]

On applique l'algorithme glouton aux sommets restants.

Étape 3 de l'algorithme de Wigderson

Histoire[modifier | modifier le code]

L'algorithme a été publié en 1983 par Avi Wigderson[1].

Notes et références[modifier | modifier le code]

  1. Avi Wigderson, « Improving the Performance Guarantee for Approximate Graph Coloring », Journal of the ACM, vol. 30, no 4,‎ , p. 729-735 (DOI 10.1145/2157.2158)