Notre but ici est de montrer que le problème de coloration avec trois couleurs est NP-complet que ce soit dans le cas des graphes planaire ou non planaire. Nous souhaitons le prouver pour le cas des graphes quelconque et pour le cas des graphes planaires. Ces résultats sont dus à Garey, Johnson et Stockmeyer.
Dans un autre exercice, on s’intéresse à une approximation du problème des 3 couleurs.
Exercice
On appelle coloration d’un graphe une fonction des sommets du graphe vers les entiers tels que deux sommets adjacents ne sont pas assignés le même entier. Le problème des 3 couleurs noté 3-COL prend en entré un graphe et répond vrai si et seulement si il existe une coloration du graphe utilisant moins de trois couleurs. Autrement dit, telle qu’il existe un fonction de coloration dont l’image est incluse dans ${1,2,3}$.
$1.$ Montrer que 3-COL est un problème dans NP.
Pour montrer que le problème est NP-difficile, on cherche à effectuer une réduction à partir de 3-SAT. Pour ce faire, une considère une formule $\varphi$ sous forme normale conjonctive dont toutes les clauses ont exactement trois littéraux. On note : $\varphi = \bigwedge\limits_{i=1}^{n}C_i$ et $C_i = (x_{1}^{i},x_{2}^{i},x_{3}^{i})$.
On veut maintenant construire un graphe qui est 3 coloriable si et seulement si $\varphi$ est satisfiable. Pour commencer on ajoute pour chaque variable et chaque négation de variable un sommet. Notre but est que pour chaque couple de variable et sa négation la couleur d’un des deux sommets corresponde à la valuation Vrai et la couleur d’un autre sommet corresponde à la valuation Faux.
$2.$ On souhaite que la fonction de coloration de notre graphe, si elle existe, soit une fonction de distribution de valeur de vérité. Donner une façon de s’en assurer.
Intéressons nous au gadget suivant :
$3.$ Que peut-on dire de la couleur du sommet $e$ en fonction des couleurs de $a$ et $b$ lorsqu’on se limite à $3$ couleurs ?
$4.$ En déduire un gadget tel qu’un sommet donné puisse être à la couleur de Vrai si et seulement si une clause et satisfaite. Donc si et seulement si une des variables de la clause soit coloré par la couleur associé à Vrai.
$5.$ Terminer la réduction.
$6.$ Montrer maintenant que pour tout $k$, $k$-COL est NP-complet.
Intéressons nous maintenant au cas planaire. On dit qu’un graphe est planaire si dans une de ses représentations graphique dans le plan, aucune arête ne se croise. Le théorème des quatre couleurs nous dit que tout graphe de ce type est 4-coloriable. Cependant, savoir si un tel graphe est 3-coloriable est NP-complet. Ce problème est appelé PLANAR-3-COL.
$7.$ Montrer que PLANAR-3-COL est dans NP.
On considère le gadget suivant :
$8.$ Montrer que pour tout 3-coloration $c$ correcte de ce gadget, on a nécessairement $c(a)=c(m)$ et $c(e)=c(i)$.
$9.$ Montrer que dans un graphe quelconque, on peut remplacer chacune de ses intersections par ce gadget et s’assurer que non seulement le nouveau graphe obtenue est planaire mais en plus il est 3-coloriable si et seulement si le graphe initial l’est.
$10.$ Conclure
$11.$ Expliquer en quelques mots pourquoi on ne peut pas adapter cette démonstration pour montrer que PLANAR-4-COL est NP-complet ?
Correction
$1.$ Si on dispose d’une $3$ coloration d’un graphe, un simple parcours du graphe nous permet de vérifier si elle est correcte. De ce fait on a un certificat de taille polynomiale en la taille de notre graphe qui permet de vérifier qu’un graphe est $3$-coloriable. On en déduit que 3-COL est dans NP.
$2.$ On crée trois sommets nommés $V$, $F$ et $A$ reliés entre eux. De plus, pour chaque variable $v_i$ de notre graphe on crée deux sommets nommés $v_i$ et $\bar{v_i}$. On ajoute alors les arêtes $(v_i,\bar{v_i}), (v_i,A), (A,\bar{v_i})$. Ainsi, chaque variable est soit de la même couleur que $V$ et sa négation de la couleur de $F$ soit l’inverse.
$3.$ Pour une coloration valide $c$, si $c(a) = c(b)$ alors $c(a) = c(e)$. De ce fait, si les couleurs de $a$ et $b$ sont soit celle de $V$ soit celle de $F$, alors $c(e)$ ne peut être égale à $c(V)$ que si $c(a) = c(V)$ ou $c(b) = c(V)$.
$4.$ On vient de construire un gadget permettant de calculer, $a \vee b$. Il nous suffit donc de le répéter. Ainsi si une clause $C$ s’écrit $(x_1 \vee x_2 \vee x_3)$ on peut considérer le gadget suivant :
Pour toute 3-coloration $c$ tel que $c(x_1)$, $c(x_2)$, $c(x_3)$ sont dans ${c(V),c(F)}$, on a $c(i) = c(V)$ seulement si il existe $1 \leq k \leq 3$ tel que $c(x_k) = c(V)$. En effet, si $c(i) = c(V)$ et $c(h) = c(F)$ alors $c(x_3) = c(V)$. Si $c(g) = c(F)$ alors $c(e) \neq c(F)$ et soit $c(x_1)$ soit $c(x_2)$ égale à $c(V)$.
De plus si on a $1 \leq k \leq 3$ tel que $c(x_k) = c(V)$ alors on a une coloration telle que $c(i) = c(V)$.
$5.$ Pour chaque clause $C_k$ on construit le gadget précédent. Pour les $x_i$ on utilise évidemment les sommets de variables déjà créés. Sinon, on associe à chacun les sommets $c_k$, $d_k$, $e_k$, $g_k$, $h_k$, $i_k$. Enfin, il nous suffit de rajouter pour tous $k$ les arêtes $(i_k,A)$ et $(i_k,F)$.
Ainsi, supposons que $\varphi$ soit satisfiable. On considère la coloration suivante : on associe à $F$ la couleur $0$, à $V$ la couleur $1$ et à $A$ la couleur $2$. On considère la distribution de valeur qui satisfait $\varphi$. Pour chaque variable $x_i$ on lui associe $1$ si elle est à vrai et $0$ sinon. Ensuite, comme cette distribution assure que pour chaque clause au moins une des variables soit de couleur $1$ on s’assure qu’on peut colorier chaque gadget de telle sorte à ce que tous les $i_k$ soient de couleur $1$. Ainsi deux sommets reliés sont de couleurs différentes et on a bien une 3-coloration de notre graphe.
Réciproquement, si notre graphe est 3-coloriable, cela signifie que tous les $i_k$ sont de la même couleur que $V$. De plus, comme les couleurs des $x_j$ sont dans ${c(V),\:c(F)}$, car voisins de $A$, on a prouvé qu’un des trois sommets initiaux de chaque gadget est de la même couleur que $c(V)$. De ce fait, si on met à vrai tous les littéraux de la même couleur que $V$ et les autres à faux, on s’assure qu’au moins un littéral par clause soit à vrai et que donc notre formule soit bien satisfaite.
Ainsi, on a construis un graphe de taille polynomiale en la taille de notre formule qui est $3$ coloriable si et seulement si $\varphi$ est satisfiable. On a donc bien montré que 3-COL est NP-complet.
$6.$ Pour montrer que pour tout $k \geq 4$, $k$-COL est NP-complet, on effectue une réduction à partir de $3$-COL. On considère un graphe $G$. On ajoute $k-3$ sommets tous reliés entre eux et reliés à tous les autres sommets de $G$ Le nouveau graphe obtenue est $k$ coloriable si et seulement si $G$ est 3 coloriable. Notons que notre réduction est bien polynomiale car $k$ n’est pas un paramètre du problème.
$7.$ Comme pour $3$-COL, il nous suffit de considérer comme certificat une coloration correcte du graphe.
$8.$ On considère une coloration correcte $c$ de notre gadget. On commence par appeler $1$ la couleur de $g$ et $2$ la couleur du sommet $c$. En effet, comme $g$ et $c$ sont liés par une arête, on sait qu’ils sont de couleurs différentes. Ainsi, on a nécessairement $c(f) = 3$, $c(h) = 3$ et $c(k) = 2$. Il nous reste alors deux choix pour colorier $b$. Soit $c(b) = 1$, soit $c(b) = 3$. Dans les deux cas, la coloration des derniers sommets est forcée et nous nous retrouvons dans une de ces deux configurations :
On a donc bien toujours $c(a)=c(m)$ et $c(e)=c(i)$.
$9.$ On considère les sommets $u,v,u’,v’$ et la situation suivante :
On remplace cette occurence par :
Il nous suffit alors de remplacer toutes les intersections en commençant par l’intersection la plus en haut à gauche. De ce fait, le graphe ainsi construit est planaire et est $3$ coloriable si et seulement si le graphe initial l’est.
$10.$ Il nous reste à montrer que notre transformation est bien de taille polynomiale. On note que cette transformation fonctionne pour toute représentation de notre graphe initial tel qu’aucune arête ne passe par un autre sommet. On considère uniquement des arêtes représenté par un segment du plan. Ainsi, tout couple d’arête ne se croise qu’au plus une fois. On ajoute donc $\displaystyle O\left(n^{2}\right)$ de sommets et d’arêtes.
Il en résulte donc qu’on a obtenu une réduction polynomiale de $3$-COL à PLANAR-$3$-COL qui est dans NP. Ainsi, PLANAR-$3$-COL est NP-complet.
$11.$ Le gadget qu’on a construit repose sur le fait qu’on colorie avec au plus $3$ couleurs. Ainsi, si on voulait pouvoir adapter cette démonstration il nous faudrait trouver un autre gadget jouant le même rôle pour un nombre plus élevés de couleurs. Cependant, on note que tout graphe planaire est $4$ coloriable donc on sait qu’un tel gadget n’existe pas car il existe des graphes non planaires qui ne sont pas $4$ coloriables.
Exercices en lien
- Coloration de Wigderson : Une coloration approximative d’un graphe 3 coloriable.