Étiquette : graphes

Isomorphismes de graphes, ou la non-trivialité de « est-ce que ce graphe est identique à celui-ci ? »

Publié le par Balise1 commentaire

Tiens, ça fait longtemps que j’ai pas causé de maths ici. Il y a eu des actualités intéressantes très récemment, alors je vais en parler un peu, en espérant pas dire trop de bêtises parce que ça commence à toucher à des trucs que je maîtrise moins 🙂

Il y a à peu près un an, László Babai, mathématicien-avec-une-bonne-dose-d’informaticien a fait l’équivalent des (très) gros titres dans le monde de l’informatique théorique avec un article intitulé Graph Isomorphism in Quasipolynomial Time ou, en français, « Isomorphisme de graphes en temps quasipolynomial » (Je vais citer Langelot Pickpocket : « C’est très facile d’écrire l’anglais. Il n’y a qu’à renverser l’ordre des noms et des adjectifs. »). Il y a quelques jours, le même László Babai a publié sur son blog un « oops, en fait ça passe pas » (c’est-à-dire une rétractation partielle du papier, il y avait une erreur dans l’analyse qui ne permettait pas de conclure à un temps quasi-polynomial). Aujourd’hui, alors même que je retournais voir cette page pour ajouter un lien vers mon blog, je vois que le temps quasi-polynomial est de nouveau sur le tapis ! C’est plus palpitant que Game of Thrones, cette histoire 😉

Bon, là, normalement, j’ai perdu mes trois lecteurs. Snif. Revenez, les gens, jvais expliquer un peu de quoi on cause… D’abord, petite question : est-ce que ces deux graphes sont identiques ?

isomorphisme-1

Normalement, c’est le moment où vous me dites « ben, ça dépend… ça veut dire quoi, identique ? » – ce à quoi je réponds « ben, ça dépend de la définition qu’on choisit, en fait ».

J’utilise ici le terme « identique » pour dire « isomorphe », ce qui est un abus de langage mais un que je m’autorise. Isomorphe, c’est un mot blindé de grec, comme l’indique le « ph » (ouais, je fais de l’approximation liguistique aussi) : préfixe « iso » – même, et « morphe » – forme. Donc, « graphes isomorphes » : graphes qui ont la même tête. Là, j’en ai deux qui se disent « elle se paye ma fiole », parce que les deux graphes ci-dessus, ils ont pas vraiment la même tête, à froid comme ça.

Mais si je les affiche comme ça, est-ce que c’est mieux ?

isomorphisme-2

Avec des petits numéros, je peux dire que :

  • 1 est relié à 3, 4 et 5
  • 2 est relié à 3,4 et 5
  • 3 est relié à 1, 2, 4 et 5
  • 4 est relié à 1, 2, 3 et 5
  • 5 est relié à 1, 2, 3 et 4

et ce sur les deux graphes. C’est ce qu’on entend par « isomorphisme de graphe » : on peut associer chaque sommet du premier graphe à un sommet du deuxième graphe de sorte que si les sommets u et v sont reliés par un arc dans le premier graphe, alors ils sont reliés par un arc dans le deuxième graphe, et vice-versa. Et la question à laquelle Babai s’intéresse, c’est « quelle est la complexité algorithmique de décider si deux graphes sont isomorphes ? »

Il existe des cas où la réponse est « les deux graphes ne sont pas isomorphes » de manière immédiate. Parmi ces cas :

  • les graphes n’ont pas le même nombre de sommets
  • les graphes n’ont pas le même nombre d’arcs
  • il existe un sommet de degré k dans le premier graphe mais pas dans le second (le degré d’un sommet, c’est le nombre d’arcs qui y sont connectés)
  • le premier graphe a une structure, par exemple quatre sommets tous reliés les uns aux autres, qui n’existe pas dans le deuxième graphe

Il existe aussi un algorithme simple pour conclure à la question : numéroter tous les sommets du premier graphe, et essayer toutes les numérotations des sommets du deuxième graphe. Si on en trouve une qui marche, c’est gagné, et si on n’en trouve pas, c’est que les graphes ne sont pas isomorphes. Le problème de cet algorithme là, c’est qu’il réclame un temps d’exécution de n! (factorielle n), où n est le nombre de sommets. De manière générale, les algorithmes avec une factorielle au milieu, on n’aime pas trop.

Le problème est intéressant à – au moins – deux titres. Le premier, c’est qu’il arrive de résoudre des instances du problème dans la vraie vie, en chimie (identifier des composés dans une base de données) ou en électronique (vérifier qu’un circuit intégré est équivalent à son schéma). Comme on fait ça de manière quotidienne, c’est pas forcément le point critique. Le second titre, c’est que le problème « Graph Isomorphism » (GI, pour son petit nom) fait partie de cet ensemble de problèmes qu’on sait pas trop où mettre, d’un point de vue complexité. Il est dans NP – il suffit de fournir un étiquetage des sommets pour vérifier que deux graphes sont effectivement isomorphes – mais personne ne sait s’il est NP-complet (« aussi difficile que tous les autres problèmes de la classe NP »). Une hypothèse usuelle est que, si P est différent de NP, GI se trouve quelque part entre P et les problèmes NP-complets.

Jusqu’à l’an passé, la borne la plus basse qu’on avait pour la complexité de GI était e^{O(\sqrt{n \log n})}. La borne annoncée, puis rétractée, puis rétablie, est e^{\log^cn} pour une constante c. Et là, pour le coup, je l’avoue sans honte – je « sais » que le deuxième est très petit devant le premier (pour n suffisamment grand, s’entend), mais il faut que j’y réfléchisse à deux fois. Quant au fait que  e^{\log^cn} corresponde à « quasi-polynomial »… bon, e^{C \log n} est polynomial, e^{n^\varepsilon} est exponentiel, l’autre est quelque part entre les deux… Ça reste une gymnastique qui ne m’est pas évidente. Il reste que du point de vue théorique, passer d’un algo exponentiel (même modérément exponentiel) à un algo qui est non seulement sub-exponentiel mais quasi-polynomial, c’est classe.

J’ai un peu pipoté quand je parlais des problèmes de la vraie vie. Parce qu’il faut également l’admettre, d’un point de vue pratique, suivant la tronche de la constante c, il faut avoir un très, très (très) gros graphe avant que le « nouveau » résultat ne « vaille le coup » (sans même parler de la complexité implémentatoire dudit algo !). Les instances de la vraie vie, elles, restent probablement beaucoup plus simples et rapides à résoudre à grands coups d’heuristiques et de bourrinage.

J’aimerais être capable de dire « mais bon, j’ai lu la preuve et c’est très joli ». Parce que le papier, je l’ai ouvert, j’ai fait « AAAAAH », et je l’ai refermé. La vidéo de la conf de Babai, je l’ai regardée dans une espèce d’état second « alors c’est probablement très intéressant, mais je comprends quedalle ». Une version mise à jour du papier original (avec les corrections nécessaires) est apparemment en cours de rédaction ; j’ai comme vague projet d’essayer d’attaquer la compréhension de ce truc à un moment ou à un autre (avec assez peu d’optimisme sur le résultat final 😉 ).

TPA : Théorème de Ramsey

Publié le par Balise2 commentaires

Je viens de me rendre compte que j’avais pas encore parlé de théorie de Ramsey dans ce blog, ce qui est profondément scandaleux, parce que c’est un sujet très rigolo. Donc, commençons – aujourd’hui, c’est TPA.

Supposons que nous ayons un graphe dit « complet », c’est-à-dire qu’on se donne un ensemble de sommets, et qu’on trace tous les arcs possibles entre tous les sommets. On dénote par K_n le graphe complet sur n sommets - par exemple, je vous présente K_5 :

 

k5-mono

Maintenant, on va colorier les arcs du graphe en rouge et en bleu, de façon arbitraire. On peut par exemple colorier tous les arcs en bleus, tous les arcs en rouge, ou choisir d’autres coloriages :

Et avec ce coloriage, on se pose une première question : est-ce qu’il est possible d’avoir un coloriage tel qu’on ne puisse pas trouver dans la figure un triangle bleu ou un triangle rouge, c’est-à-dire trois sommets reliés uniquement par des arcs bleus ou rouges ? Les deux du haut ne fonctionnent clairement pas (puisque tous les sommets sont reliés par des arcs bleus et rouges respectivement). Le coloriage en bas à gauche ne fonctionne pas non plus : il a un triangle bleu et un triangle rouge (vous les voyez ?). Le coloriage en bas à droite n’a pas de triangle rouge, mais il a un triangle bleu.

Pour 5 points, ce n’est pas très difficile de finir par trouver un coloriage qui ne contient ni triangle bleu ni triangle rouge, et c’est celui-ci :

k5-notriangle

L’étape suivante est de se poser la même question non pas avec un graphe complet sur 5 sommets (K_5) mais avec un graphe complet sur 6 sommets (K_6), comme celui-ci :

k6

Et la réponse est non, ce n’est pas possible : on ne peut pas colorier une K_6 avec deux couleurs en évitant d’avoir un triangle monochromatique (tout bleu ou tout rouge, donc). La première remarque qu’on peut faire, c’est que pour vérifier par force brute que c’est effectivement le cas, ça va prendre un petit peu de temps. Le graphe ci-dessus a 15 arcs, ce qui correspond à 2^{15} coloriages différents. Pour voir ça, on peut choisir un ordre pour les arcs (n’importe quel ordre) et commencer à colorier. Pour le premier arc, on peut choisir rouge ou bleu, ça fait deux choix. Pour le deuxième arc, idem – et on a déjà quatre choix avec deux arcs, puisqu’ils peuvent être tous les deux rouges, tous les deux bleus, rouge-bleu ou bleu-rouge. Le troisième choix multiplie encore ces choix par deux (puisque chaque choix peut correspondre à un troisième arc rouge ou bleu), et ainsi de suite pour les 15 arcs, soit 2×2×2×…×2 = 2^{15}. 2^{15}, ça fait 32768. À la main, ça va faire beaucoup de coloriages à vérifier, mais sur un ordinateur, ça reste encore nettement dans le domaine du faisable.

Avant de programmer le coloriage et de vérifier, on peut se demander s’il y aurait moyen de prouver qu’il y a toujours un triangle monochromatique dans une K_6 coloriée avec 2 couleurs. Donc, on prend un coloriage, n’importe lequel. On prend un sommet, n’importe lequel aussi. Ce sommet, il a 5 arcs qui y sont connectés, et parmi ces cinq arcs, il y en a au moins trois qui sont de la même couleur (parce que si j’ai au plus deux arcs bleus ET au plus deux arcs rouges, ben j’ai au plus 4 arcs). Pour faire simple, je vais supposer que les trois arcs qui sont de la même couleur sont bleus (je peux toujours faire ça, si ce n’est pas le cas il suffit de remplacer rouge par bleu et bleu par rouge dans ce qui suit). Maintenant on fait une petite figure avec des notations.

k6-firstcolors

J’ai au moins trois arcs bleus qui partent de mon sommet initial, j’en choisis exactement trois (les deux autres peuvent être rouges ou bleus). Ces arcs définissent trois points sur le graphe, qui sont les autres extrémités des trois arcs ; je nomme ces points u, v et w. Et là, il peut se passer plusieurs choses. Si l’arc entre u et v est bleu, alors j’ai un triangle bleu. Si l’arc entre v et w est bleu, alors j’ai un triangle bleu. Si l’arc entre u et w est bleu, alors j’ai un triangle bleu. Et si rien de tout ça ne se passe…

k6-plusred

ben l’arc entre u et v est rouge, l’arc entre v et w est rouge, et l’arc entre w et u est rouge aussi, donc le triangle défini par u, v, w est tout rouge. Tout ce que j’ai raconté là s’applique à n’importe quel coloriage (même s’il faut éventuellement changer rouge en bleu et bleu en rouge), et donc on ne peut pas trouver de coloriage qui n’ait ni triangle bleu, ni triangle rouge.

La remarque suivante, c’est que n’importe quelle K_n (c’est-à-dire un graphe complet sur n sommets), pour n \geq 6, contient une K_6. Donc si on ne peut pas colorier une K_6 sans avoir de triangle monochromatique, on ne peut pas non plus colorier une K_n, n\geq 6 sans triangle monochromatique.

Donc, pour les triangles, on sait ce qu’il se passe : pour n\leq 5, on peut trouver un coloriage tel qu’on ne trouve pas de triangle monochromatique, et pour n \geq 6, on a prouvé qu’il n’existait pas.

La question suivante est : maintenant qu’on a des choses pour les triangles, est-ce qu’on peut avoir le même genre de résultat pour plus de points ? Plus spécifiquement, si je considère une K_n, est-ce que je peux la colorier avec deux couleurs de manière à éviter d’y trouver une K_4, K_5, K_6, K_{42} de la même couleur (remarquons qu’un triangle est une K_3 😉 )? Et ben, c’est une question compliquée. Pour être sûr de trouver une K_4, il a été prouvé qu’on a besoin de 18 points. Ce qui veut dire qu’on peut colorier ce bidule-là avec 2 couleurs et ne pas y trouver de K_4 monochromatique:

K17

Si on rajoute un sommet et qu’on le connecte à tous les autres, par contre, on est sûr de trouver une K_4 monochromatique si on colorie avec deux couleurs. Là, pour le coup, si on veut réellement vérifier tous les coloriages possibles, il va vraiment falloir faire des progrès sur la puissance informatique. Une K_{18} (un graphe complet sur 18 sommets, donc) a 153 arcs, donc si on se mettait en tête de vérifier tous les coloriages, il faudrait en vérifier 2^{153}. Si on est capable de vérifier un coloriage par nanoseconde (ce qui n’est pas franchement réaliste), il faudrait plus de 3 000 000 000 000 000 000 000 000 000 (3 suivi de 27 zéros) SIÈCLES pour tout vérifier… on est pas rendu 🙂

Là où ça devient VRAIMENT amusant, c’est quand on se pose la question de trouver des K_5 et supérieur (qui soient monochromatiques, donc). Pour la K_5, on sait que pour plus de 49 sommets, on la trouvera nécessairement. On sait aussi qu’on peut construire un coloriage sur 42 sommets sans K_5 monochromatique. Le lecteur attentif aura remarqué qu’on ne sait pas ce qu’il se passe entre 43 et 49 sommets… La situation est de moins en moins claire au fur et à mesure : pour la K_{10} monochromatique, on sait que le seuil se situe quelque part entre 798 (pour 797 sommets on sait qu’on peut colorier sans avoir de K_{10} monochromatique) et… 23556 (pour un graphe complet sur 23556 sommets colorié avec deux couleurs, on sait qu’on aura toujours une K_{10} monochromatique).

Le théorème de Ramsey qui donne son nom à ce billet de blog dit que quelque soit r, on peut trouver un n tel que tout coloriage avec deux couleurs d’une K_n contienne nécessairement une K_r monochromatique. Ledit théorème est plus général que ça : il dit que pour tout r_1, r_2, r_3... r_\ell on peut trouver un n tel que tout coloriage de K_n avec \ell couleurs c_1, c_2,..., c_\ell contient ou bien une K_{r_1} de couleur c_1, ou bien une K_{r_2} de couleur c_2, …, ou bien une K_{r_\ell} de couleur c_\ell. Et on dénote n par R(r_1, r_2,..., r_\ell). (Pour rattacher aux trucs précédents, j’ai démontré que R(3,3) = 6, et j’ai indiqué que R(4,4) = 18, 43 \leq R(5,5) \leq 49 et que 798 \leq R(10,10) \leq 23556.

On peut exprimer ça de façon plus « philosophique » en disant qu’une structure suffisamment grande aura toujours un peu d’ordre local quelque part. Ce que je trouve personnellement assez fascinant.

Le mot de la fin revient à Joel Spencer: « Erdős nous a demandé d’imaginer une force d’extraterrestres, beaucoup plus puissante que nous, qui atterrit sur Terre et nous demande la valeur de R(5,5), ou bien ils détruisent la planète. Dans ce cas, dit-il, nous devrions combiner la puissance de tous nos ordinateurs et de tous nos mathématiciens pour tenter de trouver la valeur. Mais supposons qu’ils demandent R(6,6). Dans ce cas, il pense qu’il faudrait détruire les extraterrestres. » (traduction personnelle).

TPA : Mincut, maxflow et réseaux de distribution d’eau

Publié le par Balise2 commentaires

Je viens de regarder une vidéo intitulée Efficient Maximum Flow Algorithms (en anglais), et comme je me demandais depuis quelques jours ce dont je pourrais bien parler dans un TPA, c’est arrivé à point nommé. Donc, aujourd’hui, on va parler de « max flow » ou, en français, « flot maximum ». Commençons par donner un petit exemple. Supposons qu’on veuille trimbaler de l’eau depuis un point A à un point B. Pour cela, on dispose d’un réseau de tuyaux qui ont tous une certaine capacité, en terme de nombre de litres par seconde qui peuvent y circuler, et on se pose la question de savoir combien de litres par seconde peuvent arriver au point A. Faisons un petit dessin :

On a le point A, le point B, quelques points intermédiaires reliés par des tuyaux, et la capacité de chaque tuyau est indiquée sur chaque tuyau. Sur un « petit » réseau comme celui-ci, on peut s’en sortir en regardant très fort le schéma et en tentant de répartir l’eau au maximum dans les tuyaux de façon à ce qu’aucun tuyau ne soit en surcapacité, sinon ça explose et ça fait désordre (spoiler : sauf erreur grossière de ma part, on arrive avec ce réseau à 5600 litres par seconde).

Évidemment, plus le réseau est compliqué, plus le calcul l’est, et au-delà d’une certaine taille ça devient franchement pénible à faire à la main. Beaucoup de gens se sont intéressés au problème, qui est à la fois considéré comme un problème « classique » voire « résolu » (par exemple la bibliothèque C++ Boost a quelques implémentations pour le résoudre), et comme un domaine actif de recherche (il est, par exemple, en couverture du numéro d’août des Communications of the ACM). Au lieu de parler de litres d’eau et de tuyaux, on utilise notre modèle préféré, qui est celui d’un graphe (comme le laisse vaguement sous-entendre mon petit schéma au-dessus) ; le type de graphe qu’on considère a cependant quelques éléments supplémentaires par rapport aux graphes que nous avons manipulés jusqu’ici, par exemple lorsque nous avons parlé du théorème des cinq couleurs. On a, comme d’habitude, des sommets (les points A, B et les points intermédiaires) et des arcs (les tuyaux). Dans les sommets, on a deux sommets « spéciaux », les points A et B, que l’on appelle la source et le puits. Sur les arcs, on a deux informations supplémentaires : la direction, représentée sur le schéma par une flèche (on dit que le graphe est dirigé) et la capacité. Et on veut trimbaler une certaine quantité de trucs, c’est-à-dire un « flot », de A à B. Le problème peut donc être formulé comme « étant donné un graphe dirigé, dont les arcs ont des capacités, et étant donnés une source et un puits, quelle est la quantité maximum de flot qui peut être transportée de A à B ? ». Les algorithmes permettant de répondre à cette question ne sont pas forcément très compliqués, mais ils sont plus longs que ce que j’ai envie de détailler ici. Il en existe plusieurs, et il peut être intéressant de ne pas utiliser les mêmes en fonction du graphe considéré (on n’utilisera par exemple pas forcément le même algorithme pour un graphe ayant peu ou beaucoup d’arcs).

Considérons maintenant un autre problème. Supposons que j’aie une fuite massive d’eau en B, et que je veuille couper l’eau qui arrive en B en coupant la circulation dans des tuyaux, et ce de la manière la plus « efficace » possible. L’efficacité, dans mon exemple imaginaire, se mesure en débit total des tuyaux que je coupe : je veux le minimiser, pour que la reprise du service soit la plus facile possible. Quels tuyaux dois-je couper ? Il faut impérativement que je coupe le tuyau direct à 4000 entre A et B (sinon j’ai forcément de l’eau qui continue à arriver en B). Je peux couper tout ce qui arrive en B : j’ai deux tuyaux à 1000 et un à 900, ça fait un « coût » total de 2900. Mais en regardant d’un peu plus près mon graphe, plutôt que de couper l’arrivée en B, si je coupe les départs en A (hors la ligne à 4000, qui est coupée quoi qu’il arrive), je peux m’en sortir pour 2300, c’est mieux. Et en regardant d’encore plus près, si au lieu de couper le tuyau à 2000 je coupe celui à 500 et celui à 800, je descends à 1600 (300 + 500 + 800). Coïncidence amusante, si je fais la somme de tous les tuyaux que je coupe (4000+300+500+800), j’obtiens le même nombre que le nombre maximum de litres que je peux faire circuler dans mon réseau entre A et B, c’est à dire 5600.

Il se trouve que ce n’est pas une coïncidence. Ce second problème est connu sous le nom de « min cut » ou, en français, « coupe minimum » : étant donné un graphe avec des coûts ou poids sur les arcs, comment déconnecter deux points donnés A et B en supprimant des arcs de manière à ce que la somme de leurs poids soit minimum ? Et étant donné un graphe dirigé avec des capacités/poids, le théorème dit « min cut/max flow » dit que, pour toutes les paires de sommets A et B du graphe, la quantité maximum de flot qui peut aller de A à B est égale au poids minimum des arcs à supprimer pour déconnecter A et B. Pour donner une idée de la preuve, on peut voir qu’une coupe (un ensemble d’arcs qui, lorsqu’on les supprime, déconnecte A et B) est un goulot d’étranglement : il est impossible de faire passer plus de flot entre A et B que la capacité des arcs qui forment cette coupe. Ça permet de déduire que le flot maximum est forcément inférieur (ou égal) au poids de la coupe minimum. L’autre direction (montrer que la valeur de la coupe minimum est effectivement atteinte) est un peu plus délicate. L’idée est que si on a un flot maximum, alors on a des arcs qui sont saturés, c’est-à-dire que pour que le flot puisse passer de A à B, il faut faire passer une valeur de flot égale à la capacité de l’arc par l’arc en question. Si ce n’était pas le cas, on pourrait augmenter le flot, ce qui ne peut pas arriver (puisqu’on considère un flot maximum). On peut aussi voir que tous les chemins de A à B contiennent au moins un arc saturé – sinon, on pourrait augmenter le flot sur le chemin en question. Maintenant, on explore le graphe en partant de A, en avançant sur tous les chemins possibles, et on marque tous les sommets que l’on peut atteindre sans passer par un arc saturé. Si on retire tous les arcs qui partent de cet ensemble de sommets marqués vers l’ensemble des sommets non-marqués, on obtient une coupe (sinon il existerait un chemin de A à B contenant un arc non saturé). De plus, ces arcs sont saturés, et la somme de leur poids est exactement la valeur du flot maximum (puisqu’il s’agit de l’ensemble des arcs qui sortent de l’ensemble des sommets marqués). Donc la valeur de flot maximum est égale à la valeur d’une coupe, elle-même supérieure ou égale à la valeur de la coupe minimum. Tout ceci nous permet de déduire que la valeur de la coupe minimum est égale à la valeur du flot maximum (puisqu’elle lui est à la fois inférieure ou égale et supérieure ou égale), et donc on est contents. Pour une certaine définition de « contents » – l’idée de la preuve que j’ai donnée ici n’est pas des plus rigoureuse (en espérant qu’elle soit correcte, il a fallu que je m’y reprenne à trois ou quatre fois…), mais j’espère en avoir donné tout de même une idée raisonnable !

TPA : Théorème des cinq couleurs

Publié le par Balise6 commentaires

Aujourd’hui, c’est coloriage. Je vais déjà commencer par vous montrer un petit jeu : ça s’appelle Map, c’est tout con : le jeu vous donne une carte rectangulaire avec des zones à colorier, et quelques couleurs déjà placées ; il faut colorier les autres de façon à ce que deux voisins n’aient pas la même couleur. Allez-y, allez jouer un peu avec, c’est rigolo 😛 La question théorique derrière ce petit jeu est la suivante : quel est le nombre minimal de couleurs nécessaires pour pouvoir colorier n’importe quelle carte de ce type ? Peut-être que vous vous souvenez, mais j’ai déjà un peu parlé de problèmes de ce genre là : quand j’ai parlé de P vs NP, j’ai parlé de colorabilité de graphes, et de décider si un graphe donné pouvait être colorié avec un nombre donné de couleurs. La question du nombre minimum de couleurs peut revenir à poser la question précédente plusieurs fois : « et avec 2 couleurs, ça passe ? non ? et avec trois ? non plus ? et avec quatre ? ah, cool. » Là, normalement, j’ai deux objections dans la salle. La première, c’est : « minute papillon, tu parlais de cartes et là tu me parles de graphes, c’est pas pareil, si ? ». La deuxième, c’est « heu, dis voir, demander si un graphe peut être colorié avec trois couleurs, on a vu dans le P vs NP que c’était pas trivial comme question… donc on fait quoi, surtout qu’il y a peut-être beaucoup de nombres à considérer ? ». Il se trouve que la première objection permet de répondre à la deuxième. Pour répondre à la première objection, je vais faire un petit dessin. Voilà le petit dessin. map   Le petit dessin en question, il est fait comme suit :

  • j’ai commencé par dessiner la carte – la structure en noir ;
  • j’ai ajouté un point dans chaque zone de la carte (les points rouges) ;
  • j’ai relié deux points (avec les traits rouges) si les zones correspondantes étaient voisines.

NORMALEMENT j’ai vérifié ma construction, mais si elle est bancale (si j’ai des traits en trop ou en pas assez), merci de me le signaler 🙂 Et là, que voit-on apparaître en rouge sous nos yeux ébahis ? Un graphe. Pas n’importe quel graphe, d’ailleurs : il s’agit d’un graphe planaire, c’est à dire qu’on peut le dessiner sur une feuille de papier sans que deux arcs se croisent. J’ai parlé de graphes planaires dans un billet de blog précédent : Planarité, mineurs et donuts. Là, il va falloir que vous me fassiez confiance sur quelques points. Primo, la construction ci-dessus est toujours possible. Deuzio, ça donne toujours un graphe planaire. Tertio, ce graphe planaire est unique pour une carte donnée : il a toujours le même nombre de sommets, et les arcs sont toujours les mêmes. Et c’est là qu’on répond à la deuxième objection. Oui, dans le cas général, décider si un graphe peut être colorié avec 3, 4, 5 ou 12 couleurs est difficile (au stade actuel de nos connaissances). Par contre, dans le cas particulier des graphes planaires, on sait plus de choses. Plus précisément, on connaît le théorème suivant, appelé « théorème des 4 couleurs » :

Tout graphe planaire peut être colorié avec au maximum 4 couleurs.

Et, comme corollaire au point précédent, je peux colorier une carte avec quatre couleurs (il suffit de faire ma petite construction là-haut, de colorier le graphe résultant, et de colorier chaque zone avec la couleur du sommet en question – rappelons que dans le cas qui nous intéresse, un coloriage est valide si deux sommets reliés par un arc n’ont pas la même couleur.) Un petit aparté: je parle de « cartes » ici, mais c’est pas vraiment applicable directement « dans la vraie vie ». Le problème principal, c’est que certains pays ne sont pas « connectés ». Et si on colorie une carte du monde, on s’attend à ce que, par exemple, la Guyane soit de la même couleur que la France. Ce qui ajoute des arcs entre la zone « France » et les zones « Brésil » et « Suriname », et qui risque fort de nuire à la planarité du graphe correspondant. Fin de l’aparté, revenons à nos moutons. Donc, si j’ai un graphe planaire, je peux répondre directement à la question « est-ce que ce graphe peut être colorié avec k couleurs » par « oui », dès que k est supérieur ou égal à 4. La preuve du théorème des quatre couleurs est… compliquée. J’en parlerai dans un prochain billet, mais il faut que je me documente encore un peu avant sur le sujet 🙂

Un résultat intéressant est que pour trois couleurs, même dans le cas « graphe planaire », le problème reste NP-complet ! (C’est un résultat de Stockmeyer en 1973, dans un article intitulé « Planar 3-colorability is polynomial complete », qui 40 ans plus tard est toujours planqué en tant qu’article payant à l’ACM. Mais je digresse.) Donc, pour 3 couleurs, c’est dur à décider, pour 4 couleurs, on sait qu’on peut le faire, mais c’est dur à prouver. En revanche, le théorème suivant est relativement simple à prouver :

Tout graphe planaire peut être colorié avec au maximum 5 couleurs.

J’ai dit que c’était relativement simple à prouver, et donc je vais le faire. Ça va quand même être probablement un peu long, donc accrochez-vous, et je vais essayer de faire preuve de pédagogie 🙂

J’ai besoin d’un premier résultat pour ma preuve :

Tout graphe planaire contient au moins un sommet de degré au plus 5.

Le degré d’un sommet, c’est le nombre d’arcs qui y sont connectés. Comme un arc connecte exactement deux sommets, si je fais la somme des degrés de tous les sommets, j’obtiens deux fois le nombre d’arcs (parce qu’un arc donné est compté exactement deux fois, une fois à chacune de ses extrémités). Maintenant, je vais vous demander d’admettre encore un truc, c’est qu’on connaît le nombre maximal d’arcs d’un graphe planaire, en fonction de son nombre de sommets, n : il y a au plus 3n-6 arcs, dès qu’il y a plus de deux sommets (comme on me l’a fait remarquer en commentaire). Je pourrais aussi le démontrer, mais ça implique encore un résultat intermédiaire, et ce billet va finir par être vraiment beaucoup trop long (dit-elle au bout de deux pages). Comme j’ai au plus 3n-6 arcs, la somme des degrés de tous les arcs d’un graphe planaire est inférieure ou égale à 6n-12. Par conséquent, il y a au moins un sommet de degré au plus 5 : si ce n’est pas le cas, la somme des degrés de tous les arcs est supérieure ou égale à 6n (6 arcs, multipliés par n sommets), et ce n’est pas possible pour un graphe planaire.

Revenons à nos moutons initiaux : on veut maintenant démontrer que tout graphe planaire peut être colorié avec au maximum 5 couleurs. On va faire un raisonnement par récurrence sur le nombre de sommets du graphe. J’ai interrompu la rédaction de ce billet pour aller faire un billet sur le raisonnement par récurrence, allez le lire si le terme ne vous est pas ou plus clair 🙂 Donc, on commence par traiter l’hypothèse de base. Si mon graphe n’a qu’un seul sommet, je peux le colorier avec au maximum 5 couleurs : j’en choisis une pour mon sommet, et voilà.

Maintenant, je suppose que l’hypothèse de récurrence suivante est vraie : tout graphe planaire à (n-1) sommets peut être colorié avec au maximum 5 couleurs. Le but du jeu est maintenant de déduire, à partir de ça, que tout graphe planaire à n sommets peut être colorié avec au maximum 5 couleurs. Pour ça, on considère un graphe à n sommets, n’importe lequel (si je démontre que ça marche pour n’importe quel graphe, je montre que ça marche pour tous les graphes). Par le résultat intermédiaire que j’ai prouvé au-dessus, le graphe à n sommets étant planaire, il a un sommet de degré inférieur ou égal à 5, qu’on va appeler v dans la suite pour aller vite. On peut prendre v, et le retirer temporairement (on retire aussi tous les arcs qui y sont connectés). Le graphe sans v est un graphe planaire à (n-1) sommets. Donc, on peut le colorier avec au maximum 5 couleurs. Maintenant, on remet v (et les arcs qu’on a retirés aussi) : on obtient un graphe à n sommets dont (n-1) sommets sont coloriés avec au maximum 5 couleurs, et un sommet, v, n’a pas encore de couleur.

Là, on a deux possibilités. Si les voisins de v (les sommets auxquels v est connecté) utilisent moins de 5 couleurs, on peut utiliser une des couleurs non utilisées pour colorier v, et le graphe initial est colorié avec au maximum cinq couleurs.

Sinon, si on prend une représentation plane du graphe planaire, on est dans la situation suivante :

fiveneighbors Je n’ai dessiné ici que six sommets, v et ses cinq voisins. Le graphe peut contenir plus de sommets et plus d’arcs, mais il contient forcément cette structure.

Sur ma représentation plane, je choisis arbitrairement un voisin de v, je l’appelle v1, et je numérote les autres dans le sens des aiguilles d’une montre (v2 à v5). Les sommets v1 à v5 sont de cinq couleurs différentes. Je vais maintenant prouver que je peux soit colorier v1 et v3 de la même couleur, soit colorier v2 et v4 de la même couleur.

Je regarde d’abord v1 et v3, et plus précisément je m’intéresse au sous-graphe colorié avec les couleurs de v1 et de v3, c’est-à-dire que je prends tous les sommets de la couleur de v1 (gris, sur la figure) et tous les sommets de la couleur de v3 (bleu, sur la figure), et tous les arcs du graphe initial qui relient ces sommets entre eux. Un exemple sur un petit graphe :

subgraphÀ droite, j’ai représenté le sous-graphe du graphe de gauche en ne prenant que les sommets bleus et gris (j’ai supprimé les sommets rouges et violets, et les arcs qui y étaient attachés). Sur ma figure, j’ai quatre sommets entre lesquels j’ai des chemins (une suite d’arcs qui me permettent de passer de l’un à l’autre), et un sommet qui n’a de chemin vers aucun autre.

Si je ne regarde que les sous-graphe bleu/gris de mon graphe initial, j’ai deux possibilités : soit v1 et v3 ne sont plus connectés, soit ils le sont encore ; et par « connectés », j’entends qu’il y a un chemin entre v1 et v3. S’il n’y a pas de chemin, v1 et v3 sont dans des composants différents (un composant, c’est un ensemble de sommets qui sont reliés les uns aux autres par des chemins). Dans ce cas là, je regarde le composant qui contient v3 (il se peut que ce soit v3 tout seul, mais sinon c’est un ensemble de sommets bleus et gris qui ont tous un chemin connecté à v3). Dans ce composant-là, le fait que les sommets soient bleus ou gris est arbitraire : je peux inverser les deux couleurs sans que ça ait un impact sur le fait que le graphe est correctement colorié. Si je ne fais ça que dans ce composant là, v1 (qui n’est pas dans composant en question) reste gris, et v3 (qui était bleu) devient gris. Maintenant, je peux remettre le « reste » du graphe (les sommets rouges, violets, verts, et le sommet v qui n’est pas encore colorié) : comme je n’ajoute pas de sommets bleus ou gris, le coloriage reste valide. Et j’ai « libéré » le bleu pour mon sommet v : donc, je peux colorier v en bleu. La vie est belle.

Enfin, presque. Parce qu’il se peut aussi que v1 et v3 soient dans le même composant « bleu/gris ». Donc là, si j’inverse le bleu et le gris, ben je me retrouve avec v1 en bleu, et v3 en gris, et je peux toujours rien faire avec v. Donc, il faut trouver une autre astuce.

Je regarde maintenant le sous-graphe composé des sommets coloriés avec les couleurs de v2 (rouge) et v4 (vert) : je retire tout ce qui n’est pas rouge ou vert du graphe, et je regarde ce qui reste. Si v2 et v4 ne sont pas dans le même composant rouge/vert, je peux inverser le rouge et le vert dans le composant de v4. v2 reste rouge, v4 devient rouge, et je peux colorier v en vert. Là, j’ai peut-être quelqu’un qui me dit « oui, mais si v2 et v4 sont aussi dans le même composant, tu as le même raisonnement et donc le même problème que pour le composant bleu/gris ! ». Oui, mais. Regardons un peu ce qui se passe sur la figure. Comme v1 et v3 sont dans le même composant bleu/gris (sinon, on n’aurait pas besoin de regarder ce qui se passe dans le composant rouge/vert), il y a un chemin entre v1 et v3 composé de sommets bleus et gris.

bluegreypath

Si je veux faire un chemin composé de sommets verts et rouges entre v2 et v4 (ce qui est la condition pour que v2 et v4 soient dans le même composant rouge/vert), ça bloque : soit je dois croiser l’arc entre v et v3, soit je dois croiser un des arcs du chemin bleu/gris entre v1 et v3. Et comme mon graphe est plan… ben j’ai pas de croisement entre mes arcs. Donc, v2 et v4 ne peuvent pas être dans le même composant, donc je peux bien inverser les couleurs du composant de v4, et colorier v en vert.

J’ai donc regardé tous les cas possibles pour mon graphe, et dans tous les cas, je peux colorier le sommet v de façon valide. Donc, si un graphe avec (n-1) sommets peut être colorié avec au maximum 5 couleurs, alors un graphe avec n sommets peut être colorié avec au maximum 5 couleurs, ce qui termine mon étape de récurrence et donc la preuve du théorème des cinq couleurs. Ouf.

J’avais initialement prévu de parler du théorème des 4 couleurs plus en détail dans ce billet, mais je crois que je vais arrêter là pour ne pas fumer plus de neurones de mon lectorat (en espérant qu’il y en ait quand même une partie qui soit arrivée jusqu’ici…). Comme d’habitude, pour les questions, typos, remarques, etc., c’est dans les commentaires que ça se passe 🙂

TPA – Planarité, mineurs et donuts

Publié le par Balise3 commentaires

Pour le premier Théorème à Périodicité Aléatoire, on va parler de graphes, et on va faire des petits dessins. Un graphe est un ensemble de sommets reliés entre eux par des arcs. Pour décrire un graphe, je peux par exemple dire « il a les sommets 1, 2, 3, 4 et 5, et des arcs entre les sommets 1 et 2, 2 et 3, 3 et 4, 4 et 1, 1 et 3, 2 et 4, 1 et 5, et 4 et 5 ». Je peux aussi décider de le dessiner sur une feuille de papier, et je peux dessiner ça de plusieurs manières : tous les dessins, là, sont une représentation de ce graphe.

wagner1

Dans ces trois représentations, deux sont dites planes : le graphe est dessiné de façon à ce que les arcs du graphe ne se croisent pas. La première représentation n’est pas plane : les arcs 1-3 et 2-4 se croisent. Un graphe qui peut être dessiné dans le plan (c’est-à-dire sur une feuille de papier plate) sans que deux arcs se croisent est un graphe planaire. Le fait qu’on ait un adjectif pour ça devrait vous faire dire qu’il existe des graphes non planaires, c’est-à-dire qu’on ne peut pas dessiner dans le plan sans croiser deux arcs. Deux exemples classiques (et utiles pour la suite) de ce type de graphes sont le graphe complet sur 5 sommets (je prends 5 sommets et j’ajoute tous les arcs possibles), qu’on appelle en abrégé K_5, et le graphe bipartite complet sur 3×2 sommets (je prends deux groupes A et B de trois sommets et j’ajoute tous les arcs possibles entre les sommets du groupe A et les sommets du groupe B), qu’on appelle en abrégé K_{3,3}. En voici des représentations dans le plan ; comme on l’a vu, ces représentations ne sont pas uniques, mais vous pouvez chercher longtemps avant de trouver une représentation où deux arcs ne se croisent pas.

k5k33

Et le théorème suivant, dû à Wagner en 1937, dit que si un graphe n’est pas planaire, c’est parce que, quelque part dans sa structure, on trouve un truc qui ressemble à K_5 ou à K_{3,3}. Plus précisément :

Un graphe est planaire si et seulement s’il ne contient le mineur K_5 ni le mineur K_{3,3}.

Je triche un peu, parce que je n’ai pas encore défini la notion de mineur. Donc, définissons :

Un mineur d’un graphe G est un graphe obtenu à partir de G en effectuant zéro ou plusieurs suppression d’arc, suppression de sommet ou contraction d’arc.

Supprimer un arc, c’est facile : si deux points sont reliés par un arc, on peut décider qu’en fait non, et supprimer l’arc. Supprimer un sommet, c’est facile aussi : on choisit un sommet, on le supprime, et on supprime aussi tous les arcs qui y sont reliés, parce que sinon on sait pas où ils vont de toute façon. La notion de contraction est un tout petit peu plus sioux. L’idée, c’est qu’on prend deux sommets reliés par un arc, et qu’on les transforme en un seul sommet. Le sommet résultant est attaché à tous les arcs qui étaient dans le graphe précédent. On peut imaginer qu’on « pince » deux sommets qui se rapprochent, qui se rapprochent, qui se rapprochent et POUF qui n’en font plus qu’un. Un petit exemple, dans lequel je contracte l’arc rouge et dans lequel j’obtiens le sommet rouge :

contraction

Donc, en gros, ce que Wagner dit, c’est que « si je bricole mon graphe un peu et que j’arrive à faire apparaître K_5 ou K_{3,3}, alors je ne peux pas dessiner le graphe sans croisement. Par contre, si je ne peux pas faire apparaître K_5 ou K_{3,3}, alors je peux dessiner le graphe sans croisement. »

Il se trouve qu’il existe un théorème qui généralise cette idée de « mineurs exclus » – c’est un théorème de Robertson et Seymour dont la preuve prend… 20 articles, publiés de 1983 à 2004. Le théorème s’énonce comme suit :

Toute famille de graphe fermée pour les mineurs peut être décrite par un ensemble fini de mineurs exclus.

Explications : une famille de graphes fermée pour les mineurs, c’est un ensemble de graphes tels que, si je prends un graphe quelconque de cet ensemble, que j’en prends un mineur (avec la définition précédemment donnée), alors le mineur est aussi dans la famille en question. Ce que Robertson et Seymour disent, c’est que dans une famille comme ça, il existe un ensemble fini de mineurs exclus, c’est-à-dire que si on trouve ce mineur dans un graphe, alors le graphe ne fait pas partie de la famille.

Appliquons ça à l’exemple des graphes planaires. Les graphes planaires sont une famille de graphes fermée pour les mineurs : si je prends un mineur d’un graphe planaire, je peux toujours dessiner le mineur en question dans le plan sans avoir de croisement d’arc. Et les mineurs exclus sont K_5 et K_{3,3} : si je trouve ces mineurs dans le graphe, le graphe n’est pas planaire. Wagner est plus « puissant » que Robertson & Seymour pour les graphes planaires, parce qu’il donne les mineurs exclus explicitement.

Là où ça devient drôle, c’est qu’en général, on ne connaît pas les mineurs exclus en question. On sait qu’ils existe, on sait qu’il y en a un nombre fini, mais on ne sait pas quelle tête ils ont. Un petit exemple pour terminer : supposons que je veuille dessiner mon graphe non pas sur une feuille de papier, mais sur un tore – un donut, si ça vous parle plus.

donutL’idée, ça serait que je dessine des points sur mon donut, et que je les relie avec des arcs, exactement comme je le fais dans le plan. Si je fais ça, et que j’arrive à dessiner mon graphe sans croiser d’arcs, j’ai un graphe non pas planaire, mais toroïdal (ou donutidal, si vous voulez). La famille des graphes toroïdaux est fermée pour les mineurs, donc il existe une famille de mineurs exclus pour cette famille. Jusqu’à présent, on en a trouvé plus de 16 000. Et on ne sait pas combien il y en a au total. Amusant, non ?

(Et si vous voulez essayer de tous les trouver, je crois qu’il faut commencer par faire des donuts 😉 )

Problèmes NP-complets

Publié le par Balise5 commentaires

Dans un billet précédent, j’ai tenté d’expliquer avec brio (je vous laisse choisir le verbe qualifié par « avec brio ») le problème « P = NP ». J’y ai donné une définition de la classe NP, que je répète ici : NP est la classe des problèmes pour lesquels, pour chaque instance de type « oui », on peut me convaincre en temps polynomial que la réponse est « oui » en me fournissant une preuve que c’est effectivement le cas. Et en fin de billet, j’ai vaguement mentionné la notion de problème NP-complet.

La définition usuelle de problème NP-complet, c’est un problème qui est « dans NP » et « NP-difficile ». Je vais donc expliquer ce que veut dire NP-difficile 🙂 De façon informelle, c’est un problème qui est au moins aussi difficile que tous les problèmes de la classe NP. Une autre façon informelle de dire ça, c’est qu’il est aussi difficile qu’un autre problème NP-difficile. Le problème de cette définition, c’est qu’il faut bien commencer quelque part, et avoir un premier problème NP-difficile pour le comparer aux autres.

L’archétype des problèmes NP-difficiles (et donc NP-complets, parce que SAT est dans NP), c’est le problème SAT, dont j’ai parlé dans le billet précédent. C’est pas évident, a priori, que SAT est NP-difficile. Mais on peut montrer que même 3-SAT est NP-difficile : 3-SAT représente les instances de SAT où toutes les clauses ont exactement trois littéraux ((Les avis diffèrent sur la terminologie exacte. De nombreux auteurs définissent 3-SAT comme les instances de SAT où toutes les clauses ont au plus deux littéraux. J’appelle ça (sur la suggestion de mon prof de SAT) <=3-SAT. Dans le cas présent ça m’arrange de définir sur exactement 3 littéraux, donc je fais ça, OK ?)). Je ne vais en pas expliquer la preuve, parce que ça impliquerait que je passe pas mal de temps à expliquer des choses que j’ai pas fondamentalement envie d’expliquer. Pour les gens intéressés par la question, ça a été démontré en 1971 et c’est connu sous le nom de Théorème de Cook-Levin.

Maintenant qu’on en a un, on peut en trouver d’autres par réduction. On réduit un problème NP-difficile (par exemple SAT) à un autre problème qu’on veut prouver NP-difficile, appelons le A. Pour faire ça, on démontre que si on peut résoudre A efficacement, c’est-à-dire en temps polynomial, alors on peut résoudre SAT efficacement.

L’idée générale de ce genre de preuve, c’est qu’on prend une instance quelconque du problème NP-difficile, et on la transforme, en temps polynomial, en instance du problème A qui permette de conclure sur l’instance originale. Maintenant, supposons qu’on sache résoudre le problème A (c’est-à-dire n’importe quelle instance du problème A) en temps polynomial. Alors on peut prendre n’importe quelle instance de SAT, la transformer en une instance du problème A, résoudre l’instance du problème A, et conclure. La transformation se fait en temps polynomial, la résolution de A se fait en temps polynomial, la somme des deux est polynomiale, donc on sait résoudre n’importe quelle instance de SAT en temps polynomial, donc on sait résoudre SAT en temps polynomial. Facile.

Les problèmes NP-complets sont donc, en quelque sorte, « équivalents » en terme de complexité : si on sait en résoudre un en temps polynomial, alors on peut résoudre tous les autres en temps polynomial aussi, et on peut résoudre tous les problèmes de NP en temps polynomial (puisqu’ils sont aussi difficiles que tous les problèmes de la classe NP). Donc, si on trouve un moyen de résoudre en temps polynomial toutes les instances d’un problème NP-complet… on a démontré que P = NP. Et gagné un million de dollars. Et surpris beaucoup, beaucoup de monde.

Il y a toute une série de problèmes pour lesquels on sait qu’ils sont NP-difficiles, ou NP-complets si en plus ils sont dans NP. Il y a des gens qui s’intéressent à des problèmes… exotiques, dirons-nous ; je vais juste laisser quelques liens pour les gens intéressés et que ça fera rigoler :

Passé cet interlude amusant, je vais donner un exemple de réduction pour prouver que le problème CLIQUE est NP-complet. C’est probablement l’exemple bateau que tout le monde donne quand il parle de ce genre de chose, mais il doit y avoir une raison à ça (la raison en est que le problème est raisonnablement facile à décrire et que la réduction est relativement simple par rapport à ce qu’on peut voir ailleurs). Le truc que j’explique ici est largement repompé du CLRS, c’est-à-dire le Cormen, Leiserson, Rivest & Stein, c’est-à-dire Introduction to Algorithms, traduit en français sous le nom Algorithmique (je ne sais pas ce que vaut cette traduction) – c’est le bouquin de référence de BEAUCOUP de cours d’algorithmique.

Donc, le problème CLIQUE est le suivant : étant donné un graphe (un ensemble de sommets et d’arcs) G, contient-il une clique de taille k ? Une clique de taille k, c’est un ensemble de k sommets qui sont tous reliés les uns aux autres. Par exemple (vous m’excuserez, je recycle mes figures), ce machin-là est est une clique de taille 8. Notons au passage qu’il contient également une clique de taille 1 (un seul sommet), 2 (un arc), 3 (un triangle), 4, 5, 6 et 7, puisqu’on peut trouver des ensembles de sommets de cette taille qui sont tous reliés les uns aux autres.

8clique

On veut réduire 3-SAT à ce problème ; comme 3-SAT est NP-difficile, CLIQUE est NP-difficile aussi. CLIQUE est dans NP, parce que si je donne k sommets, c’est facile de vérifier que ces k sommets sont effectivement tous reliés les uns aux autres. Donc, si CLIQUE est NP-difficile, CLIQUE est NP-complet.

Pour attaquer ma réduction, je prends une formule 3-SAT. Je prends une formule 3-SAT CNF (j’ai expliqué ce que ça veut dire dans mon article sur SAT), c’est-à-dire une formule qui a cette tête là :

(x_1 \vee x_2 \vee x_3) \wedge (\bar x_2 \vee x_4 \vee \bar x_5) \wedge (x_1 \vee \bar x_2 \vee \bar x_3) \wedge ...

c’est-à-dire un ensemble de m clauses composées d’au plus 3 littéraux reliés par des OU, et les clauses étant reliées par des ET.

À partir de là, on crée un graphe contenant 3*m sommets. Chacun de ces sommets correspond à un littéral de la formule, éventuellement dupliqué. Pour visualiser les choses plus facilement, ça peut peut-être aider de grouper les sommets en groupes de trois. Dans l’exemple de la formule ci-dessus, ça donne les sommets suivants :

x_1, x_2, x_3~;\bar x_2, x_4, \bar x_5~; x_1, \bar x_2, \bar x_3

Ensuite, on ajoute des arcs partout. Enfin, presque partout. On n’ajoute pas d’arcs dans les « groupes » correspondant aux clauses. On n’ajoute pas non plus d’arcs entre les littéraux qui ne sont pas « compatibles », c’est-à-dire l’inverse l’un de l’autre. Si j’ai deux littéraux x_1 et \bar x_1, je ne crée pas d’arc entre eux. Pour ma mini-formule au-dessus, voilà ce que donne le graphe en question :

clique3sat1

et voilà les arcs qui ne sont PAS dans le graphe précédent :

clique3sat2

Et maintenant qu’on a ce graphe là, l’idée, c’est que la formule SAT peut être satisfaite si et seulement si le graphe (le premier) a une clique de taille m (m étant le nombre de clauses de la formule SAT). J’ai donc deux choses à prouver :

  • si la formule peut être satisfaite, alors le graphe a une clique de taille m
  • si le graphe a une clique de taille m, la formule peut être satisfaite.

On va commencer par le premier point. Supposons que la formule puisse être satisfaite. Donc, on peut affecter une valeur à toutes les variables de sorte que la formule soit satisfaite. Par conséquent, toutes les clauses peuvent être satisfaites par cette affectation. Donc, dans chaque clause, il existe un littéral qui a pour valeur 1 (le littéral « positif », par exemple x_1 si la variable a la valeur 1, le littéral « négatif », par exemple \bar x_1 si la variable a la valeur 0). On considère, dans chaque « groupe » de sommets du graphe défini précédemment, le sommet correspondant à ce littéral (si plusieurs littéraux ont la valeur 1, on en prend un au pif). Comme on prend un sommet par groupe, et qu’on a m groupes, on arrive à m sommets. On veut maintenant montrer qu’il y a un arc entre toutes les paires de sommets de cet ensemble de sommets. Or, les deux raisons pour lesquelles on pourrait ne pas en avoir, c’est soit que les sommets sont dans le même groupe, soit qu’ils sont incompatibles. On ne peut pas avoir choisi deux sommets dans le même groupe, puisqu’on en a choisi exactement un par groupe. Et on ne peut pas avoir choisi deux sommets incompatibles, parce qu’ils correspondraient à des littéraux x_i et \bar x_i, qu’on n’a choisi que des littéraux qui ont la valeur 1, et qu’on ne peut pas avoir en même temps x_i = 1 et \bar x_i = 1. Donc, toutes les paires dans les m sommets sont connectées entre elles, donc on a une clique de taille m, ce qu’on voulait démontrer.

Donc, on peut passer au deuxième point : si le graphe a une clique de taille m, la formule peut être satisfaite. Supposons, donc, que le graphe ait une clique de taille m. Comme les sommets d’un même groupe ne sont pas connectés entre eux, les sommets sont forcément dans des groupes différents. Si on a une clique de taille m, ça veut dire qu’on a un sommet dans chaque groupe de sommets. On peut donner à tous ces sommets la valeur 1. On ne peut pas avoir de clique qui contienne des sommets x_i et \bar x_i, puisqu’il n’y a pas d’arc entre deux sommets de ce type et que, par définition d’une clique, il faut que tous les arcs soient présents. Donc, si une clique de taille m existe, ça veut dire qu’on a trouvé un littéral par clause qui peut valoir 1, et que tous ces littéraux sont compatibles entre eux. Et donc qu’on peut satisfaire la formule correspondant au graphe, ce qu’on voulait démontrer aussi.

Donc, si on peut résoudre CLIQUE en temps polynomial, alors on peut résoudre SAT en temps polynomial ; SAT étant NP-difficile, CLIQUE l’est aussi, et donc CLIQUE est NP-complet, ce qui termine la preuve.

Le caractère NP-complet d’un problème est, quelque part, une « preuve » de la difficulté du problème en question, mais il faut atténuer ça largement. Déjà, ça ne présume en rien de la difficulté d’une instance donnée du problème. Ça ne présume en rien de la difficulté sur une certaine classe d’instances non plus. J’explique. Dire que CLIQUE est difficile, ça ne veut pas dire que, par exemple, décider si un triangle (qui est une clique de taille 3) est dans un graphe, même un gros graphe, est difficile. Parce que je peux prendre tous les ensembles de trois sommets, regarder s’ils forment un triangle, et conclure. Les ensembles de trois sommets, il y en a à peu près n³ dans un graphe à n sommets (plus exactement, il y en a n(n-1)(n-2)/6, mais, bon, à peu près n³), du coup je peux décider ça en temps polynomial (je fais n³ opérations qui vont pas prendre des plombes, c’est-à-dire vérifier si trois arcs donnés sont effectivement dans le graphe). Du coup, je peux décider 3-CLIQUE en temps polynomial. Bon, c’est pas pour ça que je vais être millionnaire, hein. Parce que le problème CLIQUE, il se limite pas à 3. Cela dit, si je veux, je peux aussi décider 1000-CLIQUE (clique de taille 1000) en temps polynomial. Bon, c’est un polynôme de degré 1000, mais on s’en fout 🙂

Par contre, dans le cas général, je ne peux pas décider si un graphe sur n sommets contient une clique de n/2 sommets, ou n/10000 sommets, ou même log n sommets en temps polynomial avec cet algorithme qui regarde tous les groupes de taille k (donc ici k = n/2, n/10000 ou log n) et qui regarde les arcs dans le groupe, parce que ça impliquerait de faire respectivement à peu près n^{n/2}, n^{n/10000} et n^{\log n} opérations, et que dans tous les cas c’est pas polynomial. Et, de manière générale, personne ne sait si c’est possible de faire ça en temps polynomial, puisque CLIQUE est NP-complet et qu’on ne sait pas si P est égal à NP. Beaucoup de gens supposent que non, mais personne ne sait.

Même là, ça ne présume en rien de la difficulté d’une instance donnée d’un problème. Supposons qu’on me file un graphe qui se trouve contenir n(n-1)/2 arcs pour n sommets. Alors je peux décider, sans trop de problème, que oui, ce graphe contient une clique de taille n/2, n/10000 et log n. Parce qu’un graphe de n(n-1)/2 arcs pour n sommets, ben il contient tous les arcs possibles pour le graphe : c’est un graphe complet (une clique sur n sommets), et comme une clique sur k sommets est un sous-graphe d’une clique sur n sommets… ben c’est pas bien difficile de répondre à la question. Idem si on me file un graphe avec 0 arcs et n sommets, je vais pas avoir beaucoup de mal à répondre que non, il ne contient pas de clique de taille n/2.

Dans le cas de SAT, on n’a aucun problème à résoudre les instances de 2-SAT (où toutes les clauses contiennent deux littéraux) en temps polynomial (et même linéaire). Il y a aussi des instances de SAT qui sont « faciles », par exemple celles où il y a peu de dépendances entre les clauses : on sait qu’on peut les résoudre, et on sait même comment (et, pour les gens intéressés, par « peu de dépendances », j’entends « qui tombent dans le cas du Lovász local lemma, dont l’application à SAT n’est pas évidente d’après la définition de la Wikipedia, mais qui devrait être plus claire ici).

De manière générale, il peut même être non trivial de créer des instances de problèmes NP-complets qu’on ne sait pas résoudre en temps polynomial. Notons au passage que c’est pas facile de prouver qu’on ne sait pas résoudre une instance donnée en temps polynomial. On peut exhiber des instances de problèmes qui sont difficiles (i.e. exponentielles) pour un algorithme donné, et triviales pour d’autres algorithmes…

Et c’est un peu ce qui se passe en pratique : on a des instances de problèmes pour lesquels on sait que le cas général est NP-complet (ou pire), et qu’on résout pourtant tous les jours en pratique. Une des raisons peut être que le problème est « petit » (c’est pas un drame de coller un algorithme exponentiel sur un problème de taille 4, quoi), mais ça peut aussi être parce que le problème fait partie d’une sous-classe d’instances sur laquelle le problème est facile. Donc, conclure qu’une instance de problème est difficile parce que le problème général l’est et abandonner (parce qu’on saura pas faire), c’est pas forcément une bonne idée, parce qu’il se peut qu’on n’ait pas considéré qu’on se trouve dans une restriction facile du problème !

Bref, comme d’habitude, « c’est pas aussi simple que ça ». En ce moment, je fais de la théorie, et du coup je m’intéresse plutôt aux problèmes eux-mêmes plutôt qu’à des instances données. Mais c’est parfois salutaire de se souvenir que des trucs « difficiles en théorie » peuvent s’avérer « faciles en pratique », ça change des trucs faciles en théorie qu’on sait pas faire en pratique… 🙂