Apprendre le mécanisme de Réduction Polynomiale de la classe
des problèmes NP-Complet
Xavier Lorca, Cléa Martinez, Jacques Lamothe
10 décembre 2024
Résumé
Cette séance de TD de 3 heures a pour objectif de vous sensibiliser au mécanisme de réduction
polynomiale de la classe des problèmes NP-Complet. Vous apprendrez comment effectuer une réduc-
tion vous garantissant l’équivalence (au sens de la complexité) entre deux problèmes donnés. Vous
observerez comment naît une classe d’équivalence au sens de la réduction polynomiale.
1 Modéliser en SATisfaction : le rôle des formules logiques et de
3-SAT
L’objectif est ici de vous sensibiliser à la manipulation simple d’une formule logique. De façon générale,
une formule logique est formée à partir de variables propositionnelles en utilisant les trois opérateurs :
— négation (noté ¬),
— conjonction logique (noté ∧, appelée “et”),
— disjonction logique (noté ∨, appelée “ou”).
Un littéral est soit une variable propositionnelle soit la négation d’une variable propositionnelle comme a
ou ¬a. Une clause est la disjonction de un ou plusieurs littéraux. Une formule est dite en forme normale
conjonctive si elle est la conjonction de une ou plusieurs clauses. Une formule est dite satisfaisable s’il est
possible d’affecter une valeur vrai ou faux à chacune des variables propositionnelles de telle façon que la
formule soit vraie. Le paradigme de modélisation logique peut être augmenté sans difficulté par l’ajout
de l’implication, notée →, qui pourra s’exprimer de manière équivalente comme a → b ou ¬a ∨ b.
Dans ce contexte, le problème général de 3-Satisfiability se formule de la manière suivante :
3-Satisfiability
INSTANCE : Une instance φ de 3-Satisfiability avec m clauses C1 , . . . , Cm telles que Ci = (αi1 ∨αi2 ∨αi3 ),
αij un literal.
QUESTION : φ est-elle satisfaisable ?
Nous n’avons pas pour ambition de vous faire travailler la transformation du problème 3-Satisfiability
vers un machine de Turing afin de démontrer sa complexité. Nous allons simplement travailler la modé-
lisation d’un problème sous la forme d’une formule logique : il s’agit de la modélisation d’un Sudoku.
Une grille de Sudoku est une matrice n × n, composée de n2 cases, et cette grille est elle-même divisée
en `2 sous-grilles, chacune de taille ` × `, telle que n = `2 . Généralement, on prend n = 9 et ` = 3. Au
départ certaines cases sont remplies par des chiffres et d’autres sont vides. Le but du jeu est de remplir
les cases vides en respectant les règles suivantes :
— Pas deux chiffres identiques sur une même ligne ;
— Pas deux chiffres identiques sur une même colonne ;
— Pas deux chiffres identiques dans l’une des sous-grilles de taille ` × `.
Pour formaliser une instance d’un problème de Sudoku, vous aurez besoin de beaucoup de variables
propositionnelles. Ainsi, vous aurez besoin :
— n3 variables propositionnelles, notées Cxyz avec x, y et z ∈ [1, n] ;
IFIE - Optimisation Discrète -1/3- 10/12/2024
— La variable Cxyz sera vraie si et seulement si la case (x, y) contient la valeur z.
Pour n = 9, vous aurez donc à disposition n3 = 729 variables propositionnelles.
Question 1 Modélisez dans la formule A le fait que chaque case contient un et un seul chiffre. On
raisonnera pour toute colonne et toute ligne, i ∈ [1, n], j ∈ [1, n], il doit exister une valeur k ∈ [1, n] telle
que la case (i, j) contient cette valeur k et uniquement celle-ci, c’est à dire que pour toute valeur k 0 6= k,
la case (i, j) ne peut pas contenir k 0 .
Question 2 Modélisez dans la formule B le fait que l’on ne doit pas avoir deux chiffres identiques sur
une même colonne. On raisonnera pour toute colonne i ∈ [1, n], pour toutes lignes j 6= j 0 ∈ [1, n] et pour
toute valeur k ∈ [1, n], si la case (i, j) contient k, alors la case (i, j 0 ) ne contient pas k.
Question 3 Modélisez dans la formule C le fait que l’on ne doit pas avoir deux chiffres identiques sur
une même ligne. On raisonnera pour toute ligne j ∈ [1, n], pour toutes colonnes i 6= i0 ∈ [1, n] et pour
toute valeur k ∈ [1, n], si la case (i, j) contient k, alors la case (i0 , j) ne contient pas k.
Question 4 Modélisez dans la formule D le fait que l’on ne doit pas avoir deux chiffres identiques dans
l’une des sous-grilles de taille `×`. Cette formule s’exprimera aisément en identifiant les cases de chacune
des sous-grilles avec une notation spécifique de ses coordonnées, par exemple (`x , `y ), et en raisonnant
sur toute paire x, y ∈ [0; ` − 1].
Question 5 Proposez sur un exemple d’une grille de votre choix et montrez comment modéliser dans
une formule E le fait de placer les chiffres déjà inscrits dans l’instance.
Question 6 Donnez la formule générale vérifiant qu’une grille de sudoku est valide.
2 Travailler la chaîne de réduction
2.1 Independent Set
INSTANCE : Un graphe G = (V, E) et un entier k ≤ |V |.
QUESTION : Existe-t-il un ensemble de sommets de taille k tel que le sous-graphe induit ne contienne
aucune arête.
Question 7 Proposez le principe d’un algorithme vérifiant le certificat polynomial pour le problème
Independent Set. Vous utiliserez le squelette d’algorithme suivant 1 et détaillerez ensuite sa complexité
en temps et en espace.
Algorithme 1 Certificat polynomial IndependetSet
Entrées: U ⊆ V un ensemble de sommets de taille k (|k|), G = (V, E) un graphe
Sorties: retourne Oui si U est un Independent Set de G, retourne Non sinon
pour todo faire
si todo alors
todo
finsi
fin pour
todo
Question 8 Nous nous intéressons ici à transformer une formule 3-SAT, contenant m clauses, en un
graphe non-orienté. À partir d’un exemple, proposez une transformation où chaque sommet du graphe
sera associé à un littéral dans une clause de la formule.
Question 9 Pour rappel, choisir un littéral dans chaque clause d’une formule 3-SAT et choisir une
affectation de ces littéraux tels qu’ils soient tous vrais conduit à valider la formule 3-SAT considérée.
Concluez formellement la réduction polynomiale.
IFIE - Optimisation Discrète -2/3- 10/12/2024
2.2 Vertex Cover
INSTANCE : Un graphe G et un entier k ≤ |V |.
QUESTION : Existe-t-il une couverture par sommets de G de taille k ?
Question 10 Recherchez la définition de couverture d’un graphe.
Question 11 Quel lien existe-t-il entre le problème Independent Set et le problème Vertex Cover ?
Question 12 Pour la beauté de l’exercice, sur la base de l’algorithme 1, exhibez un certificat polynomial
pour le problème de Vertex Cover, c’est à dire que l’algorithme retournera oui si U est un vertex Cover
de G.
2.3 Hitting Set
INSTANCE : Une collection C = {C1 , . . . , Cm } de sous-ensembles de S, un entier k
QUESTION : Existe-t-il un ensemble S 0 ⊆ S, |S 0 | ≤ k tel que ∀i = 1 . . . m, Ci ∩ S 0 6= ∅
Question 13 Exhibez un algorithme qui sera le certificat polynomial du problème de Hitting Set.
Question 14 Quel lien existe-t-il entre le problème Vertex Cover et le problème Hitting Set ?
Question 15 Que concluez-vous sur la complexité du problème de Hitting Set ?
IFIE - Optimisation Discrète -3/3- 10/12/2024