Au Joyeux Ragondin

Le problème de coloration de graphe (peut-on colorier les sommets d'un graphe avec k couleurs sans que deux sommets voisins aient la même couleur) est un des problèmes classiques d'algorithmique qui sont connus pour être NP-complets. La célèbre conjecture (P != NP) postule que pour certains problèmes, dont les problèmes NP-complets, il n'existe pas d'algorithme les résolvant en temps polynomial. La preuve de cette conjecture permettrait de répondre, enfin, à la question "existe-t-il des problèmes difficiles". Bien entendu, cette preuve a toujours défié mathématiciens et informaticiens.

Jusqu'à recemment en tout cas. Le mois dernier, le mathématicien Edwin Eutch, se basant sur des travaux d'Alfred Tarski, a proposé un algorithme polynomial permettant de décider la k-colorabilité. Dans ce genre de cas, il ne faut pas se précipiter: de nombreuses preuves ont été avancées, et rejetées. Mais après de nombreuses relectures, l'article a été accepté et publié, ce qui est déjà beaucoup. Inutile de préciser que la communauté est en émoi.

L'article est bien entendu très technique, et je vous invite à le lire pour vous faire une opinion, mais je vais quand même en esquisser l'idée générale. L'obstacle dans tous les problèmes NP-complets est l'explosion combinatoire qui fait que l'on ne peut pas (dans un temps raisonnable) explorer tous les cas possibles. Par exemple dans le cas de la k-coloration, il est possible de vérifier toutes les colorations possibles pour un graphe donné, mais leur nombre est trop élevé pour que cela soit une technique raisonnable. Tarski et Eutch se basent sur un résultat de théorie de l'information formulé par J.P. Pernod et F. Nyues qui prétend qu'il est possible de ne considérer qu'une partie très réduite de l'information sans diminuer la qualité du résultat. L'algorithme effectue une décomposition du graphe d'entrée en un nombre réduit de sous-graphes appelés motifs, et dont on connaît le nombre chromatique. Ces motifs (dont la figure ci-dessous donne des exemples) sont ensuite recomposés sans que la coloration soit rendue impropre, et ce en temps polynomial.