3-Coloration est NP-complet
Clarence Kineider
Leçons : 915, 916, 925, 928
Référence(s) : Cormen, Leiserson, Rivest, Stein, Introduction à l’algorithmique.
On définit le problème de 3-coloration (problème de décision) :
Entrée : Un graphe non-orienté G = (V, E).
3COL Sortie : Oui si le graphe admet une 3-coloration, i.e. une application c : V → {1, 2, 3} tel que
(u, v) ∈ E ⇒ c(u) 6= c(v). Non sinon.
Théorème : Le problème 3COL est NP-complet.
Ce problème est bien dans NP : l’application c : V → {1, 2, 3} est un certificat pour ce problème, i.e. on peut
vérifier en temps polynomial si c’est une 3-coloration.
Il reste donc à montrer que 3COL est NP-dur. Pour cela, on va définir une réduction du problème 3SAT qui est
NP-dur (et même NP-complet) au problème 3COL.
Entrée : Un formule propositionnelle ϕ en forme 3-CNF.
3SAT
Sortie : Oui si ϕ est satisfiable, non sinon.
Vm
Soit ϕ une formule du calcul propositionnel en 3-CNF. On note ϕ = j=1 Cj avec Cj les clauses de ϕ. Notons
p1 , . . . , pn les variables propositionnelles qui apparaissent dans ϕ. On va construire un graphe tr(ϕ) qui sera basé
sur le graphe suivant :
v f
G
e = r
p1 ¬p1 p2 ¬p2 ... pn ¬pn
On peut remarquer que dans une 3-coloration de ce graphe, la couleur d’une variable propositionnelle p sera
toujours différente de celle de ¬p et qu’un littéral aura toujours la couleur de v ou de f , jamais de celle de r.
1
Puis, pour chaque clause C = (αC ∨ βC ∨ γC ) de ϕ, on va « coller » à G
e le gadget suivant (les sommets αC , βC ,
γC et v sont déjà dans le graphe G,
e on rajoute les autres sommets et toutes les arêtes) :
αC βC γC
xC yC
GC = zC
sC tC
Le graphe G = tr(ϕ) ainsi obtenu possède 3 + 2n + 5m sommets. La réduction tr(ϕ) est donc calculable en
temps polynomial en m, le nombre de clauses de φ (car n 6 3m).
Pour montrer que tr définit bien une réduction de 3SAT à 3COL, nous utiliserons les deux lemmes suivants :
e où pour toute clause C = (αC ∨ βC ∨ γC ) de ϕ, l’un des 3 littéraux est de la
c une 3-coloration de G
Lemme : Soit e
couleur de v. Alors on peut compléter e
c en une 3-coloration c de G.
Démonstration : Il faut montrer qu’étant donnée une telle 3-coloration de G,
e on peut la compléter en une 3-
coloration de GC pour toute clause C de ϕ. Il suffit de traiter tous les cas, il y en a 23 − 1 = 7 (n’en traiter qu’un à
l’oral).
Lemme : Soit c une 3-coloration de G. Pour toute clause C = (αC ∨ βC ∨ γC ) de ϕ, l’un des sommets αC , βC ou γC
a la couleur de v.
Démonstration : Par l’absurde, supposons que αC , βC et γC ont tous la couleur de f (on rappelle qu’ils ont soit
la couleur de v, soit celle de f ). Comme αC et βC ont la couleur de f , les sommets xC et yC ont les couleurs de r
ou v et leurs couleurs sont différentes car ils sont liés par une arête. Ainsi zC a nécessairement la couleur de f . De
même, comme zC et γC ont la couleur de f , on en déduit que v a la couleur de f . Absurde.
Proposition : Pour tout formule ϕ en 3-CNF, ϕ est satisfiable si et seulement si tr(ϕ) admet une 3-coloration.
Démonstration : Soit ϕ une formule en 3-CNF.
⇒ : Soit ν une valuation qui satisfait ϕ (on note ν |= ϕ). On fixe des couleurs différentes pour les sommets v, f et
r de G = tr(ϕ), et on colorie les sommets associés aux variables propositionnelles de ϕ de la façon suivante :
c(v) si ν(pi ) = 1 c(v) si ν(pi ) = 0
∀i ∈ {1, . . . , n}, c(pi ) = , et c(¬pi ) = .
c(f ) sinon c(f ) sinon
2
e De plus, comme ν |= ϕ = Vm Cj , on a pour tout j ∈ {1, . . . , m},
c de G.
On a ainsi obtenu une 3-coloration e j=1
ν |= Cj = (αCj ∨ βCj ∨ γCj ), donc dans chacun des gadgets GC l’un des sommets αC , βC ou γC est de la couleur de
v. Donc d’après le premier lemme, on peut compléter la coloration ec de G
e en une coloration c de G = tr(ϕ). Donc
tr(ϕ) est 3-coloriable.
⇐ : Soit c une 3-coloration de tr(ϕ). On définit une valuation ν par
1 si c(pi ) = c(v)
∀i ∈ {1, . . . , n}, ν(pi ) = .
0 sinon
D’après le deuxième lemme, dans chaque gadget GC , l’un des sommets αC , βC ou γC a la couleur de v, donc pour
tout j ∈ {1, . . . , m} ν |= Cj , donc ν |= ϕ. La formule ϕ est satisfiable.
On a donc réduit le problème 3SAT qui est NP-dur au problème 3COL en temps polynomial. Donc le problème
3COL est NP-dur.
Remarque :
On a supposé que les instances de 3SAT sont des formules ayant exactement 3 littéraux par clauses, mais si
considère que les clauses ont au plus 3 littéraux, alors on construit les gadgets GC en mettant des f à la place de
γC si C = αC ∨ βC ou βC et γC si C = αC .
Merci à David Xu pour ce développement.