Graphes et Optimisation discrète

Question 1

Représentation d'un graphe et taille des données

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.

Appartenance du problème k-COL à la classe NP

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.

1. La taille totale des données d'entrée (le graphe et le témoin) est |M| + |V| = n² + kn. Pour un graphe de grande taille (n grand), cette somme reste polynomiale et inférieure à 2|M|.
2. L'algorithme de vérification, notons-le ψ(M, V), fonctionne ainsi : il parcourt toutes les arêtes du graphe (il y en a au plus n²). Pour chaque arête reliant un noeud i à un noeud j, il vérifie dans V si la couleur du noeud i est différente de la couleur du noeud j.
3. Le nombre d'opérations effectuées par la fonction ψ est directement proportionnel au nombre d'arêtes. Le balayage prend donc un temps borné par n², ce qui est un temps polynomial par rapport à la taille de l'entrée n² + kn.

Le problème k-COL appartient donc bien à la classe NP.

Réduction polynomiale de k-COL à SAT

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 :

1. 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)

2. 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 :

• Si cet ensemble de clauses est satisfaisable : Pour chaque noeud i, la clause C_i étant vraie, il existe au moins un indice l pour lequel P(i, l) est vraie. S'il y en a plusieurs, on choisit le plus petit indice l et on attribue la couleur l au noeud i. De plus, pour toute arête (i, j), la clause A_i,j,l empêche que P(i, l) et P(j, l) soient vraies simultanément. Deux noeuds adjacents n'auront donc jamais la même couleur. Le graphe est bien k-coloriable.
• Réciproquement, si le graphe est k-coloriable : Il suffit d'attribuer la valeur Vrai à P(i, l) si le noeud i a la couleur l dans le coloriage valide, et Faux sinon. Cette affectation rend naturellement toutes les clauses C_i et A_i,j,l vraies.

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.

Question 2

Représentation des données pour p-SAT

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.

Décidabilité de 2-SAT en temps polynomial

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) :

1. Si l'on parvient à E_m (l'ensemble des clauses ne contenant plus que la variable P_m), cet ensemble est soit vide, soit composé des clauses P_m ou ¬P_m isolées. C'est évidemment satisfaisable tant qu'on n'a pas P_m et ¬P_m en même temps.
2. Raisonnons par récurrence : supposons que l'on ait fixé les variables d'indice strictement supérieur à j, rendant E_{j+1} satisfaisable. Peut-on trouver une valeur pour P_j rendant E_j satisfaisable ? Les clauses de E_j qui ne dépendent que des variables d'indice > j sont déjà dans E_{j+1} et donc satisfaites par hypothèse. Il reste les clauses impliquant P_j : elles sont de la forme (P_j ∨ P_k) ou (¬P_j ∨ P_l). Par construction de la méthode de résolution, la clause (P_k ∨ P_l), qui est une conséquence logique de (P_j ∨ P_k) et (¬P_j ∨ P_l), a été injectée dans E_{j+1} et est déjà satisfaite. Cela garantit qu'il est impossible que P_k et P_l soient faux simultanément dans E_{j+1}. Par conséquent, on ne rencontrera jamais le cas insoluble où P_j doit être Vrai (car P_k est faux) ET Faux (car P_l est faux) en même temps. Il existera toujours une affectation de P_j (soit Vrai, soit Faux) qui satisfera toutes les clauses impliquant P_j dans E_j.

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.

Équivalence polynomiale entre p-SAT et 3-SAT

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 :

• L₁ ∨ L₂ ∨ Q₃
• ¬Q₃ ∨ L₃ ∨ Q₄ (qui traduit logiquement Q₃ ⇒ L₃ ∨ Q₄)
• ¬Q₄ ∨ L₄ ∨ Q₅
• ...
• ¬Q_{p-1} ∨ L_{p-1} ∨ L_p

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.

Question 3

Algorithme polynomial pour 2-COL

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) :

1. On choisit un noeud arbitraire comme racine et on construit un arbre couvrant du graphe. S'il n'est pas connexe, on répète pour chaque composante connexe.
2. On colorie la racine en Rouge.
3. On parcourt les autres noeuds : si la distance (le nombre d'arêtes dans l'arbre) entre un noeud et la racine est paire, on le colorie en Rouge. Si elle est impaire, on le colorie en Vert.
4. Une fois l'arbre colorié, on vérifie toutes les autres arêtes du graphe original qui ne font pas partie de l'arbre. Si l'on trouve une arête reliant deux noeuds de même couleur, le graphe n'est pas 2-coloriable. Sinon, c'est un 2-coloriage valide.

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.

Équivalence polynomiale entre 3-SAT symétrique et 3-COL

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).

1. On crée un noeud neutre central nommé O.
2. Pour chaque variable P_j, on crée deux noeuds : un noeud P_j et un noeud ¬P_j, que l'on relie entre eux par une arête.
3. On relie les noeuds P_j et ¬P_j au noeud O. (Ce qui forme des triangles O - P_j - ¬P_j).
4. Pour chaque clause C_i = L_i¹ ∨ L_i² ∨ L_i³, on crée trois noeuds correspondants aux littéraux (L_i¹, L_i², L_i³) et on les relie tous entre eux pour former un triangle.
5. On relie le noeud de la clause L_i^k au noeud représentant la négation logique de sa variable. Par exemple, si le littéral L_i^k est la variable positive P_j, on ajoute une arête entre L_i^k et le noeud ¬P_j. S'il correspond à ¬P_j, on le relie à P_j.

Preuve de la réduction :

• De 3-SAT vers 3-COL : Supposons que les variables respectent la propriété Π (chaque clause a au moins un littéral Vrai et au moins un littéral Faux). On colorie O en Vert. On colorie les variables Vraies en Bleu et les Fausses en Rouge. (Chaque noeud P_j et ¬P_j aura une couleur différente entre Bleu et Rouge, car ils forment un triangle avec O qui est Vert). Pour chaque littéral de la clause, on lui donne la couleur de sa valeur de vérité (Bleu ou Rouge). L'arête le reliant à son opposé dans les variables globales ne crée pas de conflit (ex: un littéral L Vrai est Bleu, il est relié au noeud global ¬L qui est Faux donc Rouge. Bleu relié à Rouge est valide). Puisque la clause respecte la propriété Π, le triangle (L_i¹, L_i², L_i³) contiendra au moins un noeud Bleu et au moins un noeud Rouge. Il y aura inévitablement deux noeuds de même couleur dans ce triangle : pour résoudre ce conflit local, on change la couleur de l'un des deux noeuds identiques en Vert. Le coloriage devient strictement valide.
• De 3-COL vers 3-SAT : Supposons que le graphe admet un 3-coloriage valide. Sans perte de généralité, admettons que O est Vert. Les noeuds P_j et ¬P_j sont reliés entre eux et à O, ils doivent donc nécessairement prendre les couleurs Bleu et Rouge de façon exclusive. Définissons qu'être Bleu correspond à la valeur Vrai, et Rouge à Faux. Dans un triangle de clause (L_i¹, L_i², L_i³), il est impossible que les trois noeuds prennent les mêmes couleurs de variables (par exemple trois Bleus) car cela nécessiterait au moins deux Verts pour corriger le conflit, ce qui est impossible dans un simple triangle. De plus, par construction des arêtes croisées, le noeud L_i^k est contraint de ne pas adopter la couleur de la variable globale opposée. Ainsi, les littéraux dans le triangle des clauses héritent des couleurs Bleu ou Rouge des variables globales. Le fait qu'ils ne puissent pas être unicolores prouve que la clause n'a pas 3 littéraux Vrais ni 3 littéraux Faux, satisfaisant la propriété Π.

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.

Méthode

Face à une épreuve de théorie de la complexité sur l'optimisation discrète :

1. Identifiez toujours précisément le témoin : Lorsqu'on vous demande de prouver qu'un problème appartient à NP (comme pour la Question 1), la démarche est systématique. Définissez ce qui sert de solution (le témoin), évaluez la taille en mémoire de l'instance ET du témoin, puis vérifiez explicitement que l'algorithme qui vérifie ce témoin opère en temps polynomial.
2. Ne confondez pas indices et valeurs dans les réductions : La clé des questions de type SAT vers les Graphes (ou l'inverse) réside dans les variables intermédiaires. Dans la réduction SAT vers 3-COL, prenez le temps au brouillon de dessiner ce qui se passe pour une seule variable (le triangle avec O) et pour une seule clause. La mécanique des graphes (où l'arête impose "couleur différente") traduit toujours une contrainte logique (soit "Vrai ou Faux mais pas les deux", soit "au moins l'un des deux").
3. Respectez l'intuition derrière les clauses : Dans la résolution algorithmique (2-SAT, Question 2), l'idée sous-jacente est l'algorithme de Davis-Putnam. Vous devez montrer que si l'on assigne une valeur à une variable pour satisfaire une clause, cela ne déclenche pas une réaction en chaîne aboutissant à une impossibilité. C'est le coeur des preuves par récurrence sur les arbres de décision.