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}\le n$, i.e $m\le \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.