Graphes et Optimisation discrète
Graphes et Optimisation discrète
Optimisation, Graphes, Théorie de la Complexité · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
Pour représenter un graphe G à n noeuds, la méthode la plus directe est d'utiliser sa matrice d'adjacence M. Cette matrice est booléenne (composée de 0 et de 1), ce qui requiert au maximum n² bits en mémoire pour un graphe de n noeuds.
Pour représenter un coloriage spécifique de ce graphe, on utilise un vecteur V qui associe à chaque noeud sa couleur. Si l'on dispose de k couleurs (numérotées de 1 à k), la convention de l'énoncé est de représenter cette couleur en binaire unaire (par exemple, la couleur 3 est codée par 111). Il faut donc k bits par noeud, ce qui donne une taille totale de k × n bits pour le vecteur V.
Ainsi, la taille totale des données d'un graphe colorié est |M| + |V| = n² + kn bits.
Pour prouver qu'un problème de décision appartient à la classe NP (Non-déterministe Polynomial), il faut démontrer qu'une solution proposée (le témoin) peut être vérifiée par un algorithme déterministe en un temps polynomial par rapport à la taille des données d'entrée.
Ici, le témoin est le coloriage du graphe, c'est-à-dire le vecteur V.
Le problème k-COL appartient donc bien à la classe NP.
L'objectif est de traduire le problème du k-coloriage en un problème de satisfaisabilité booléenne (SAT), sans passer par le théorème de Cook, de façon à ce que le graphe soit k-coloriable si et seulement si l'ensemble de clauses créé est satisfaisable.
Nous allons définir des variables propositionnelles P(i, l) qui valent Vrai si le noeud i possède la couleur l, et Faux sinon. Il faut imposer deux règles logiques :
Chaque noeud doit avoir au moins une couleur : Pour chaque noeud i, on crée la clause C_i : C_i = P(i, 1) ∨ P(i, 2) ∨ ... ∨ P(i, k)
Deux noeuds adjacents ne peuvent pas partager la même couleur : Pour chaque arête (i, j) appartenant à l'ensemble des arêtes A, et pour chaque couleur l de 1 à k, on crée la clause A_i,j,l : A_i,j,l = ¬P(i, l) ∨ ¬P(j, l)
Preuve de l'équivalence :
Complexité spatiale : Le nombre total de clauses est n (pour les noeuds) + k × (nombre d'arêtes), soit au maximum n + k × n². Le codage de ces clauses prend de l'ordre de k × n² bits, ce qui représente bien un encombrement polynomial par rapport à la taille du graphe (n²). La réduction est donc valide.
Le problème p-SAT consiste en un ensemble de n clauses, chacune contenant p littéraux (variables ou leurs négations) choisis parmi m variables propositionnelles P₁ à Pₘ.
Pour représenter informatiquement ces données, on peut utiliser un tableau à deux dimensions de taille n lignes par p colonnes. Chaque case du tableau contient un entier identifiant le littéral. Puisqu'il y a m variables et que chaque variable peut être affirmée (P_j) ou niée (¬P_j), il existe 2m littéraux possibles. Les entiers dans le tableau seront donc compris entre 1 et 2m. La taille des données pour ce tableau sera au maximum de 2 × m × n × p bits.
Le problème 2-SAT (où chaque clause a 2 littéraux) peut être résolu en appliquant le principe de résolution logique par récurrence, en éliminant les variables l'une après l'autre. Soit E_j la liste des clauses restantes lorsqu'on ne considère plus que les variables P_j à P_m.
L'algorithme vérifie s'il est possible de déterminer des valeurs de vérité successives sans générer de contradiction (c'est-à-dire sans obtenir simultanément une clause exigeant P_k et une autre exigeant ¬P_k) :
Le nombre total de clauses possibles impliquant m variables dans 2-SAT est borné par 4m². Les opérations de balayage et de déduction logique s'effectuent donc en un temps proportionnel à la taille des données, démontrant que 2-SAT est polynomial.
Toute clause longue L₁ ∨ L₂ ∨ ... ∨ L_p peut être fragmentée en une série de petites clauses de 3 littéraux en introduisant de nouvelles variables intermédiaires (les variables Q).
On introduit (p - 3) nouvelles variables Q₃, Q₄, ..., Q_{p-1}. La variable Q_i représente sémantiquement le reste de la disjonction, c'est-à-dire L_i ∨ L_{i+1} ∨ ... ∨ L_p. La clause originale longue est équivalente à ce nouvel ensemble de (p - 2) clauses :
Si la clause d'origine est satisfaisable, on peut propager les valeurs de vérité dans les variables Q_i pour rendre toutes ces clauses de 3 éléments vraies. Inversement, si cet ensemble de 3-clauses est satisfait, la chaîne logique force au moins l'un des littéraux L₁ à L_p à être vrai, satisfaisant la clause originelle.
3-SAT est un cas particulier de p-SAT, et nous venons de prouver que tout problème p-SAT (et donc SAT en général) peut être traduit en 3-SAT. Le tableau final aura des dimensions de 3 colonnes sur n × (p - 2) lignes. La taille des données reste bornée par 6 × m × n × p, ce qui est une expansion linéaire et donc polynomiale. Puisque SAT est NP-Complet, 3-SAT (qui lui est équivalent polynomialement) l'est également.
Le problème 2-COL consiste à colorier un graphe avec seulement 2 couleurs. Une propriété fondamentale de la théorie des graphes stipule qu'un graphe est 2-coloriable (ou biparti) si et seulement s'il ne contient aucun cycle de longueur impaire.
L'algorithme polynomial pour le résoudre est simple (basé sur un parcours en largeur ou en profondeur) :
La construction de l'arbre et la vérification des arêtes parcourent chaque noeud et chaque arête un petit nombre de fois. La complexité en temps est donc proportionnelle au nombre d'arêtes (borné par n²), ce qui est bien polynomial.
L'objectif est de transformer un problème 3-SAT en un graphe qui sera 3-coloriable si et seulement si les clauses du problème 3-SAT satisfont une condition spécifique (propriété Π ou symétrie, empêchant que tous les littéraux d'une clause soient simultanément Vrais ou simultanément Faux).
Construction du graphe : On utilise 3 couleurs que l'on nommera arbitrairement Bleu (Vrai), Rouge (Faux), et Vert (Indifférent ou Outil).
Preuve de la réduction :
Puisque ce graphe a une taille proportionnelle au nombre de variables et de clauses, la traduction est polynomiale. 3-SAT étant NP-Complet, 3-COL l'est également, de même que k-COL pour tout k ≥ 3.
Face à une épreuve de théorie de la complexité sur l'optimisation discrète :