Chapitre 12: Quelques problèmes NP-complets

Ce matériel couvre plusieurs problèmes NP-complets classiques en informatique théorique et en optimisation combinatoire. Il s’adresse aux étudiants en informatique ou mathématiques souhaitant comprendre les notions fondamentales de NP-complétude, les réductions entre problèmes, ainsi que des exemples emblématiques comme SAT, STABLE, CIRCUIT HAMILTONIEN, 3-COLORABILITE, et des problèmes d’optimisation comme SAC A DOS et PARTITION.

Problèmes NP-complets autour de SAT

Définition et NP-complétude de 3-SAT

Le problème 3-SAT consiste à déterminer si une formule booléenne F, composée d’une conjonction de clauses C1 ∧ C2 ∧ ... ∧ Cm, où chaque clause Ci est une disjonction de trois littéraux (variables ou négations), est satisfaisable. Autrement dit, existe-t-il une affectation des variables x1, ..., xn dans {0,1} telle que F soit vraie ?

Le théorème fondamental est que 3-SAT est NP-complet. La preuve repose sur la réduction de SAT à 3-SAT en transformant chaque clause de longueur supérieure à 3 en une conjonction de clauses à 3 littéraux, en introduisant de nouvelles variables auxiliaires. Par exemple, une clause C = x ∨ y ∨ z ∨ u ∨ v ∨ w ∨ t est remplacée par :

(x ∨ y ∨ a) ∧ (¬a ∨ z ∨ b) ∧ (¬b ∨ u ∨ c) ∧ (¬c ∨ v ∨ d) ∧ (¬d ∨ w ∨ t)

Cette transformation est réalisable en temps polynomial et préserve la satisfiabilité.

Remarque : Le problème 2-SAT, où les clauses ont deux littéraux, est quant à lui dans P (résoluble en temps polynomial).

NAESAT et NAE3SAT

Le problème NAESAT (Not-All-Equal SAT) demande s’il existe une affectation des variables telle que dans chaque clause, au moins un littéral soit vrai et au moins un autre soit faux.

NAESAT est NP-complet, démontré par réduction de SAT à NAESAT en ajoutant une variable auxiliaire z à chaque clause. Si la formule SAT est satisfaisable, on fixe z à 0 pour obtenir une solution NAESAT. Sinon, on inverse les valeurs pour obtenir une affectation valide.

De même, NAE3SAT, la version où chaque clause contient exactement trois littéraux, est NP-complet. La réduction de NAE4SAT à NAE3SAT s’effectue en remplaçant chaque clause à 4 littéraux C = x ∨ y ∨ z ∨ t par deux clauses à 3 littéraux :

C1 = x ∨ y ∨ ¬uC
C2 = z ∨ t ∨ uC

où uC est une nouvelle variable. Cette transformation conserve la satisfiabilité NAESAT.

Problèmes NP-complets liés aux graphes

STABLE (Ensemble stable)

Un ensemble stable dans un graphe non orienté G = (V, E) est un sous-ensemble V' ⊂ V de taille k tel que pour tout couple (u, v) dans V', il n’existe pas d’arête entre u et v.

Le problème STABLE est NP-complet. La réduction se fait à partir de 3-SAT en construisant un graphe G où :

• Chaque littéral dans chaque clause correspond à un sommet.
• Des arêtes relient les sommets correspondant à une variable et son complémentaire.
• Chaque clause correspond à un triangle entre ses trois littéraux.

Un stable de taille k correspond à une affectation satisfaisant la formule 3-SAT.

CLIQUE

Une clique est un sous-ensemble de sommets de taille k où chaque paire de sommets est reliée par une arête.

CLIQUE est NP-complet, et la réduction se fait via le complémentaire du graphe : un stable dans G correspond à une clique dans le graphe complémentaire G̅.

RECOUVREMENT DE SOMMETS

Un recouvrement de sommets est un sous-ensemble V' ⊂ V de taille au plus k tel que chaque arête ait au moins une extrémité dans V'.

Ce problème est NP-complet, et la réduction s’appuie sur le complémentaire des sommets par rapport à STABLE.

COUPURE MAXIMALE

Le problème consiste à décider s’il existe une partition V = V1 ∪ V2 du graphe G telle que le nombre d’arêtes entre V1 et V2 soit au moins k.

La NP-complétude est démontrée par réduction de NAE3SAT à COUPURE MAXIMALE. Le graphe construit associe à chaque variable deux sommets (u et ¬u), avec des arêtes formant des triangles pour chaque clause. Une coupure maximale correspond à une affectation satisfaisant NAE3SAT.

CIRCUIT HAMILTONIEN

Un circuit hamiltonien est un cycle passant une fois et une seule par chaque sommet du graphe.

Le problème CIRCUIT HAMILTONIEN est NP-complet. La preuve utilise une réduction de RECOUVREMENT DE SOMMETS en construisant un graphe H où chaque arête du graphe initial est remplacée par un motif particulier admettant exactement deux chemins hamiltoniens. Un circuit hamiltonien dans H correspond à un recouvrement de sommets dans G.

VOYAGEUR DE COMMERCE

Le problème demande s’il existe une permutation π des n villes telle que la somme des distances Mπ(i)π(i+1) soit au plus k.

Il est NP-complet, démontré par réduction de CIRCUIT HAMILTONIEN en construisant une matrice de distances où :

Mi,j = 1 si (i, j) ∈ E
Mi,j = 2 sinon

Un circuit hamiltonien correspond à une permutation de coût n.

CIRCUIT LE PLUS LONG

Décider s’il existe un circuit dans G de longueur au moins r sans répéter de sommet est NP-complet. La réduction vient de CIRCUIT HAMILTONIEN en attribuant un poids 1 à chaque arête et en cherchant un circuit de longueur ≥ n.

3-COLORABILITE

Le problème consiste à décider si un graphe G est coloriable avec au plus 3 couleurs, c’est-à-dire si l’on peut assigner une couleur à chaque sommet de sorte que deux sommets adjacents n’aient pas la même couleur.

3-COLORABILITE est NP-complet. La réduction de 3-SAT à 3-COLORABILITE construit un graphe avec :

• Trois sommets VRAI, FAUX, NSP formant un triangle, chacun avec une couleur distincte.
• Pour chaque variable xi, un triangle entre xi, ¬xi et NSP, forçant xi et ¬xi à prendre des couleurs opposées VRAI ou FAUX.
• Un motif pour chaque clause x ∨ y ∨ z qui encode la contrainte qu’au moins une variable soit vraie.

Une 3-coloration correspond à une affectation satisfaisant la formule 3-SAT.

Problèmes NP-complets d’optimisation combinatoire

SOMME DE SOUS-ENSEMBLE

Étant donné un ensemble fini d’entiers E et un entier t, décider s’il existe un sous-ensemble E' ⊂ E dont la somme est égale à t.

Le problème est NP-complet. La réduction se fait à partir d’une version de RECOUVREMENT DE SOMMETS où l’on cherche une couverture de taille exactement k. On construit un ensemble d’entiers codant les sommets et les arêtes via une base b (au moins 4) pour éviter les retenues dans la somme, et on définit un entier cible t qui encode la condition de couverture.

SAC A DOS

Le problème du sac à dos consiste à décider s’il existe un sous-ensemble d’objets avec poids ai et valeurs vi, tel que la somme des poids soit au plus A et la somme des valeurs au moins V.

Il est NP-complet, démontré par réduction de SOMME DE SOUS-ENSEMBLE en posant ai = vi = ei et A = V = t.

PARTITION

Décider si un ensemble fini d’entiers E peut être partitionné en deux sous-ensembles de sommes égales.

PARTITION est NP-complet. La réduction vient de SOMME DE SOUS-ENSEMBLE en ajoutant deux entiers X = 2S et X' = S + 2t (avec S la somme des éléments de E), de sorte que la partition de E ∪ {X, X'} correspond à un sous-ensemble de E de somme t.

Glossaire des termes clés

• 3-SAT : Problème de satisfiabilité d’une formule booléenne en forme normale conjonctive avec clauses à 3 littéraux.
• NAESAT : Variante de SAT où chaque clause doit contenir au moins un littéral vrai et un littéral faux.
• Stable (ensemble stable) : Sous-ensemble de sommets d’un graphe sans arêtes entre eux.
• Clique : Sous-ensemble de sommets d’un graphe où chaque paire est reliée par une arête.
• Recouvrement de sommets : Sous-ensemble de sommets couvrant toutes les arêtes du graphe.
• Coupure maximale : Partition des sommets maximisant le nombre d’arêtes entre les deux parties.
• Circuit hamiltonien : Cycle passant une fois par chaque sommet du graphe.
• Voyageur de commerce : Trouver un cycle de coût minimal visitant toutes les villes (sommets).
• 3-colorabilité : Colorier un graphe avec 3 couleurs sans que deux sommets adjacents aient la même couleur.
• Somme de sous-ensemble : Trouver un sous-ensemble d’entiers dont la somme est égale à une valeur cible.
• Sac à dos : Sélectionner des objets pour maximiser la valeur sous contrainte de poids.
• Partition : Diviser un ensemble d’entiers en deux sous-ensembles de somme égale.

Points clés à retenir

• De nombreux problèmes classiques sont NP-complets, ce qui signifie qu’ils sont au moins aussi difficiles que SAT.
• La NP-complétude se démontre souvent par réduction polynomiale d’un problème NP-complet connu.
• Les problèmes sur les graphes (STABLE, CLIQUE, RECOUVREMENT, CIRCUIT HAMILTONIEN, 3-COLORABILITE) sont des exemples typiques de NP-complétude.
• Les problèmes d’optimisation combinatoire comme SAC A DOS et PARTITION sont également NP-complets.
• Certaines variantes plus simples, comme 2-SAT, sont résolubles en temps polynomial.
• Les réductions utilisent souvent des constructions astucieuses, comme l’introduction de variables auxiliaires ou de motifs dans les graphes.