Complexité et Calculabilité

Correction Série 10 - Problèmes

NP-Complets Episode 2 : Le Retour des
Graphes

15 Mai 2023

Pensez à justifier vos réponses.

Exercices
1. Montrez de nouveau, comme vu dans le cours, que le VERTEX-COVER
est NP-Hard, à partir du problème de la CLIQUE.

On réduit CLIQU E ∝ V ERT EX − COV ER :

Soit G = (V,E) et k le graphe et la valeur du problème de la clique.
On crée ce qu’on appelle le graphe dual de G, qu’on notera GD : il
s’agit du graphe complémentaire à G, contenant les mêmes noeuds, mais
ou l’existence des arêtes est inversé : toutes les arêtes qui existent dans
G n’existent pas dans GD , et toutes celles qui n’existaient pas dans G
existent dans GD .
On pose donc GD et N − k (ou N est le nombre de noeuds, |V |) comme
le graphe et la valeur du VERTEX-COVER.
S’il existe une clique de taille k dans G, alors aucune arête ne relie ces
noeuds dans GD . Les N − k autres noeuds sont donc un Vertex-Cover
pour GD .
De même, si N − k noeuds sont un Vertex-Cover pour GD , alors aucune
arête n’existe entre les k noeuds restants, et ces k noeuds forment donc
une clique dans G.
Enfin, cette réduction est bien polynomiale, car il suffit de construire le
graphe dual de G, ce qui prend θ(N 4 ) (Pour chaque arête possible (θ(N 2 )
arêtes), on doit parcourir les arêtes de G pour voir si cette arête existe
dans G ou non (θ(N 2 ) à chaque fois, donc θ(N 2 · N 2 = N 4 ) en tout).

1
 N5 D5

N1 N3 D1 D3

N6 D6

N2 N4 D2 D4

N7 D7

Figure 1: Clique (en vert) dans un graphe, et Vertex-Cover correspondant (en

rouge) dans le graphe dual

2. Montrez que le problème du STABLE (également appelé ”Sous-Ensemble

Indépendant”) est NP-Complet.

ˆ On commence par montrer que STABLE est NP. Il suffit de choisir

par non-déterminisme les k noeuds qui formeraient le stable (θ(n)
pour n noeuds), puis de vérifier s’il s’agit d’un stable en parcourant
les arêtes (θ(n2 )).
ˆ On réduit CLIQU E ∝ ST ABLE :
Soit G = (V,E) et k le graphe et la valeur du problème de la clique.
On crée de nouveau le graphe dual de G. Et on pose GD et k comme
le problème du stable.
S’il existe une clique de taille k dans G, alors aucune arête ne relie
ces noeuds dans GD , et donc ces mêmes k noeuds sont un Stable de
GD .
De même, si k noeuds sont un Stable pour GD , alors aucune arête
n’existe entre ces k noeuds, et donc ces k noeuds forment bien une
clique dans G.
Et cette réduction est bien polynomiale, la construction du graphe
dual prenant θ(n4 ) (c.f. exercice 1 ci-dessus).

2
 N5 D5

N1 N3 D1 D3

N6 D6

N2 N4 D2 D4

N7 D7

Figure 2: Clique (en vert) dans un graphe, et Stable correspondant (en violet)
dans le graphe dual

3. Montrez que le SOUS-GRAPHE ISOMORPHE est NP-Hard.

ˆ On réduit CHEM IN − HAM ILT ON ∝ SOU S − GRAP HE −

ISOM ORP HE :
Soit GH = (V,E), avec N = |V | le graphe du problème du chemin de
Hamilton. On définit le graphe G dans le problème du Sous-Graphe
Isomorphe comme G = GH (On copie simplement GH ), et on définit
le G′ dans le problème du Sous-Graphe Isomorphe comme un chemin
de N noeuds et N-1 arêtes (G′ = (V ′ , E ′ ) avec V ′ = {v1 , ...vn } et
E ′ = {(vi , vi + 1) , i = 1, ..., n − 1}).
Le graphe n’ayant pas changé, s’il existe un chemin dans GH , alors
le même chemin dans G est isomorphe à G’. Similairement, s’il existe
un sous-graphe G” isomorphe à G’ dans G, alors ce sous-graphe est
un chemin, et existait avant la réduction dans GH .
Et cette réduction est bien polynomiale (θ(N 2 )), la copie du graphe
prenant θ(N 2 ) et la création de G’ θ(N ) (N noeuds et N-1 arêtes
pour G’ qui est un chemin donc θ(N )).

Note : On peut très similairement réduire depuis la clique, le stable ou

le cycle de hamilton (G’ étant alors une clique, un stable ou un cycle
respectivement).
4. Montrez que le problème du 4-COLORIAGE est NP-Hard.

On fait la réduction depuis le 3-Coloriage :

Soit G = (V,E) le graphe du 3-Coloriage. Pour le 4-Coloriage, on copie
le même graphe, auquel on ajoute un nouveau noeud NX , relié à tous les

3
 autres :

G′ = (V ′ = V ∪ {NX }, E ′ = E ∪ {e = (Ni , NX ) | Ni ∈ V })

S’il existe une solution au 3-Coloriage, alors on colore NX de la 4ème

couleur, et c’est une solution pour le 4-Coloriage.
S’il n’existe pas de solution pour le 3-Coloriage, comme NX est relié à
tous les autres noeuds, il a sa propre couleur. Donc comme le reste du
graphe n’est pas coloriable en 3-couleurs, il n’y a pas non plus de solution
au 4-Coloriage.
Et cette transformation est polynomiale, car pour n noeuds, il suffit de
copier le graphe, et d’ajouter un noeud et n arêtes (θ(n2 ) pour la copie,
θ(n) pour l’ajout).

N1 N1

N2 N3 N2 N3

N4 N4 NX

N5 N6 N5 N6

N7 N7

Figure 3: Instance du 3-coloriage (gauche), instance du 4-coloriage correspon-

dant après la réduction (droite)

5. Montrez que le problème du 4-COLORIAGE-PARTIEL est NP-Complet.

ˆ On montre que le 4-Coloriage-Partiel est NP : On choisit la couleur

de chaque noeud qui n’est pas encore coloré par non-déterminisme,
puis on vérifie si pour chaque arête, les deux voisins sont bien de
couleurs différentes (θ(n2 ) pour la vérification, θ(n) pour le choix
non-déterministe).
ˆ On fait la réduction depuis le 3-Coloriage :
Soit G = (V,E) le graphe du 3-Coloriage. Pour le 4-Coloriage-Partiel,
on copie le même graphe, auquel on ajoute un nouveau noeud NX ,
relié à tous les autres :

G′ = (V ′ = V ∪ {NX }, E ′ = E ∪ {e = (Ni , NX ) | Ni ∈ V })

On fixe la couleur de ce noeud à une des 4 couleurs possibles. S’il

existe une solution au 3-Coloriage, alors c’est une solution évidente

4
 du 4-Coloriage-Partiel.
S’il n’existe pas de solution pour le 3-Coloriage, comme NX est relié
à tous les autres noeuds, il ne reste que 3 couleurs utilisables, et le
4-Coloriage-Partiel n’a donc pas non plus de solution.
Et cette transformation est polynomiale, pour les mêmes raisons que
l’exercice précédent (θ(n2 ) pour n noeuds).

N1 N1

N2 N3 N2 N3

N4 N4 NX

N5 N6 N5 N6

N7 N7

Figure 4: Instance du 3-coloriage (gauche), instance du 4-coloriage-partiel cor-

respondant après la réduction (droite)

6. A partir du problème VERTEX-COVER, montrez que le problème de la

COUVERTURE MINIMALE est NP-Complet.

ˆ On choisit de façon non-déterministe les k sous-ensembles (θ(n), par-

courir une fois l’entrée). Puis on vérifie s’ils contiennent bien tous
les éléments de l’ensemble initial (θ(n2 ), on parcourt l’entrée au pire
θ(n) fois). Le problème de couverture minimale est donc bien dans
NP.
ˆ On réduit VERTEX-COVER ∝ COUVERTURE MINIMALE : Soit
G = (V,E) et k le graphe et la taille du problème Vertex-Cover.
Pour la Couverture Minimale, on définit l’ensemble global comme
E, l’ensemble des arêtes du graphe G. Pour chaque noeud Ni du
graphe G, on définit un sous-ensemble Si = {e = (Ni , Nj ), Nj ∈
V } ∪ {e = (Nj , Ni ), Nj ∈ V } pour la couverture minimale, c’est à
dire l’ensemble des arêtes liées à Ni . Enfin, on définit le nombre de
sous-ensemble par k (le même nombre que le Vertex-Cover).
S’il existe un vertex-cover de taille k, alors ces k noeuds touchent
toutes les arêtes. Donc les k sous-ensembles correspondants sont une
couverture de E.
De même, si k sous-ensembles sont une couverture de E, alors toutes
les arêtes touchent un des k noeuds correspondants.
La réduction est polynomiale, car on copie l’ensemble des arêtes

5
(θ(n2 ) pour n noeuds), et on construit un sous-ensemble pour chaque
noeud (pour chaque noeud (n noeuds), on parcourt les arêtes (θ(n2 )),
soit θ(n3 ) en tout).