TD NP-complétude
Exercice 1 ensembles indépendants
Le problème ENS INDEP est le suivant :
entrée : un graphe G = (S, A) non orienté et k ∈ N ;
sortie : oui ssi il existe un ensemble S 0 de taille k tel que A ∩ (S 0 × S 0 ) = ∅.
On propose la transformation suivante : les occurrences des littéraux
d’une 3-forme normale conjonctive sont les sommets du graphe. On relie les
occurrences qui sont dans la même clause et aussi les occurences opposées.
1. Quel graphe obtient-on à partir de ϕ = (¬x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ z) ∧ (x ∨
y ∨ z) ∧ (¬x ∨ ¬y) ?
2. Montrer que ENS INDEP est NP-complet.
Le problème COUVERTURE SOMMET est le suivant :
entrée : un graphe G = (S, A) non orienté et k ∈ N ;
sortie : oui ssi il existe un ensemble C de taille k tel que pour tout (x, y) ∈ A,
x ∈ C ou y ∈ C.
3. Montrer que COUVERTURE SOMMET est NP-complet.
Le problème CLIQUE est le suivant :
entrée : un graphe G = (S, A) non orienté et k ∈ N ;
sortie : oui ssi il existe un ensemble C de taille k tel que pour tout C × C ⊆ A.
4. Montrer que CLIQUE est NP-complet.
5. Soit k un entier. Est-ce que le problème suivant est NP-complet ?
entrée : un graphe G = (S, A) non orienté
sortie : oui ssi il existe un ensemble C de taille k tel que pour tout C × C ⊆ A.
6. Ecrire un algorithme en O(|S|) pour résoudre CLIQUE pour des graphes
où tous les sommets sont de degré ≤ 3.
1
Exercice 2 Coloration dans un graphe eulérien
Le problème de la 3-coloration d’un graphe quelconque est NP-complet. On
s’intéresse ici à une restriction sur les entrées de ce problème.
Un graphe non orienté est eulérien si tous ses sommets sont de degré pair
(le degré d’un sommet s est le nombre d’arêtes qui contiennent s) et qu’il est
connexe. Dans la suite de cet exercice, on considérera que tous les graphes
utilisés sont connexes.
Un graphe G = (S, A) est 3-coloriable s’il existe une fonction c : S →
{0, 1, 2} tel que si (s, t) ∈ A, alors c(s) 6= c(t). On s’intéresse au problème de
la 3-coloration dans un graphe eulérien :
entrée : un graphe non orienté eulérien
sortie : oui, si le graphe est 3-coloriable.
1. Pour un graphe G = S, A quelconque, montrer que l’ensemble des sommets
S impairs peut s’écrire comme une partition {s ∈ S|deg(s) =
de degrés
1[2]} = i∈I Xi où les Xi contiennent exactement deux sommets et sont
disjoints deux à deux.
a a a
d b c d b c d b c
s
X0
e e e
À partir d’un graphe (connexe) quelconque G = (S, A), on construit G0
en ajoutant pour chaque Xi = {ai , bi }, un nouveau sommet si à S et deux
arêtes (ai , si ) et (bi , si ).
2. Montrer que le graphe G0 ainsi obtenu est eulérien.
3. Montrer que le problème de la 3-coloration dans un graphe eulérien est
NP-complet. (explicitez bien la réduction que vous faites)
2
Exercice 3 2-SAT
Le problème 3-SAT est NP-complet. Dans cet exercice, nous allons mon-
trer que si on se restreint aux formules qui sont des formes normales conjonc-
tives d’ordre 2, comme par exemple (x1 ∨ x2 ) ∧ (¬x1 ∨ x3 ) ∧ (x2 ∨ ¬x4 ) ∧ . . .
alors le problème de satisfiabilité est dans P.
On définit le problème 2-SAT de la manière suivante :
entrée : une formule φ(x1 , . . . , xn ) sous formule normale conjonctive d’ordre 2
sortie : oui ssi il existe une valuation pour x1 . . . xn qui rende φ vraie
1. En observant que la formule x ∨ y est équivalente à ¬x → y, donner un
problème équivalent sur les graphes orientés résoluble en temps polyno-
mial.
2. Conclure.
Exercice 4 Super Mario Bros
Un niveau de Super Mario bros est une matrice n × m. Chaque case de la
matrice contient soit du vide, soit une case avec un champignon qui gran-
dit, soit une case à casser, soit une case incassable, soit une tortue, soit un
champignon méchant, soit un drapeau de fin de niveau). Mario commence en
(0, 0).
On suppose connues les règles de Super Mario Bros. On s’intéresse au
problème suivant :
entrée : un niveau de Super Mario Bros
sortie : oui ssi il est possible de finir le niveau
1. Que pensez-vous du problème restreint aux instances qui ne contiennent
pas d’ennemis et ni de champignon qui grandit ?
2. Montrer que le problème est NP-complet. (penser à 3SAT)