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 $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 $G=(S,A)$ un tel graphe. On note $n$ le nombre de sommets de $G.$

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

La complexité de l'algorithme de Wigderson est polynomiale en $n$ et détermine un coloriage de $G$ qui utilise $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 $m$ le nombre de sommets traités durant le point 2, alors l'algorithme colorie au moins $m{\sqrt {n}}$ sommets. On a donc :

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

Ainsi le nombre de couleurs utilisées dans le point 2 est d'au plus $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 à ${\sqrt {n}}-1$. L'algorithme glouton utilise donc au plus ${\sqrt {n}}$ couleurs pour colorier le reste des sommets. Ainsi, le nombre de couleurs utilisées est d'au plus $3{\sqrt {n}}$, il est donc en $O({\sqrt {n}})$.

Exemple

Le graphe suivant est 3-coloriable :

Graphe 3-coloriable

Application de l'étape 2

Le sommet $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 $6$.

Après ces opérations, il n'y a plus de sommet non colorié avec au moins ${\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.

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).