Algorithme de Wigderson

L'algorithme de Wigderson est un algorithme de coloration de graphe. C'est un algorithme de complexité en temps polynomiale, qui colore avec ${\displaystyle O({\sqrt {n}})}$ couleurs les graphes 3-coloriables. Il est dû à Avi Wigderson.

Description

Cet algorithme s'effectue sur des graphes qu'on sait 3-coloriables. Soit ${\displaystyle G=(S,A)}$ un tel graphe. On note ${\displaystyle n}$ le nombre de sommets de ${\displaystyle G.}$

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

La complexité de l'algorithme de Wigderson est polynomiale en ${\displaystyle n}$ et détermine un coloriage de ${\displaystyle G}$ qui utilise ${\displaystyle O({\sqrt {n}})}$ couleurs.

Correction de l'algorithme de Wigderson

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 ${\displaystyle m}$ le nombre de sommets traités durant le point 2, alors l'algorithme colorie au moins ${\displaystyle m{\sqrt {n}}}$ sommets. On a donc :

${\displaystyle m{\sqrt {n}}\leq n}$, i.e ${\displaystyle m\leq {\sqrt {n}}}$.

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

Exemple

Le graphe suivant est 3-coloriable :

Graphe 3-coloriable

Application de l'étape 2

Le sommet ${\displaystyle 4}$ 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 ${\displaystyle 6}$.

Après ces opérations, il n'y a plus de sommet non colorié avec au moins ${\displaystyle {\sqrt {12}}}$ voisins non coloriés.

Étape 2 de l'algorithme de Wigderson

Application de l'étape 3

On applique l'algorithme glouton aux sommets restants.

Étape 3 de l'algorithme de Wigderson

Histoire

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

Notes et références

• Cet article est partiellement ou en totalité issu de l'article intitulé « Coloration de graphe » (voir la liste des auteurs).

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