Chapitre 1

Complexité des Problèmes de Satisfaction de

Contraintes Booléennes

1.1. Introduction

Un problème de satisfaction de contraintes booléennes, encore appelé problème

de satisfaisabilité, consiste, étant donné un ensemble de contraintes définies sur des
variables booléennes, à décider s’il existe une assignation de valeurs aux variables sa-
tisfaisant toutes les contraintes (et éventuellement à déterminer une telle assignation).
Souvent une telle assignation n’existe pas et, dans ce cas, il est naturel de chercher une
assignation satisfaisant un nombre maximal de contraintes, ou minimisant le nombre
de contraintes non satisfaites.

Un exemple d’un problème de satisfaction de contraintes booléennes est le pro-

blème connu sous le nom de S AT, consistant à décider si une formule propositionnelle
(exprimée comme une conjonction de disjonctions) est satisfaisable ou non. S AT a été
le premier problème montré NP-complet par Cook [COO 71] et Levin [LEV 73] et est
resté depuis un problème central dans l’étude de la NP-difficulté des problèmes d’op-
timisation [GAR 79]. La NP-complétude de S AT assure qu’aucun algorithme pour
ce problème ne peut être efficace au pire cas, sous l’hypothèse P6=NP. Néanmoins,
il existe, en pratique, de nombreux algorithmes efficaces pour résoudre le problème
S AT.

Chapitre rédigé par Cristina BAZGAN.

1
2 Optimisation Combinatoire

Les problèmes de satisfaisabilité ont des applications directes en recherche opé-

rationnelle, intelligence artificielle et architecture des systèmes. Par exemple, en re-
cherche opérationnelle, le problème de coloration de graphes, peut être modélisé comme
une instance de S AT. Pour décider si un graphe avec n sommets peut être coloré
avec k couleurs, nous considérons k × n variables booléennes, xij , i = 1, . . . , n,
j = 1, . . . , k, où xij prend la valeur vrai si et seulement si le sommet i se voit at-
tribuer la couleur j. Hoos [HOO 98] a étudié l’efficacité de diverses modélisations
du problème de coloration de graphes comme un problème de satisfaisabilité quand
on applique un algorithme de recherche locale spécifique sur l’instance du problème
de satisfaisabilité obtenue. Le problème de l’arbre de Steiner, largement étudié en re-
cherche opérationnelle, intervient dans des applications de conception de réseaux et
routage. Dans [JIA 95], les auteurs ont réduit ce problème à un problème consistant à
trouver une assignation maximisant le nombre de contraintes satisfaites. Certains pro-
blèmes d’ordonnancement ont été résolus en passant par une modélisation en termes
de problème de satisfaisabilité [CRA 94]. Tester diverses propriétés de graphes ou
hypergraphes est également un problème qui se ramène à un problème de satisfai-
sabilité. En intelligence artificielle, une application intéressante est le problème de
planification qui peut être représenté comme un ensemble de contraintes tel que toute
assignation satisfaisante correspond à un plan valide (voir [KAU 92] pour une telle
modélisation). D’autres applications en intelligence artificielle sont : l’apprentissage
à partir d’exemples, la détermination de la cohérence d’un système de règles d’une
base de connaissances, la construction d’inférences dans une base de connaissances.
Dans la conception de circuits électriques, on souhaite généralement construire un cir-
cuit avec certaines fonctionnalités (décrites par une fonction booléenne) satisfaisant
diverses contraintes motivées par des considérations technologiques, de fiabilité ou de
disponibilité comme par exemple : minimiser le nombre de portes utilisées, minimiser
la profondeur du circuit, ou n’utiliser que certains types de portes.

Les problèmes de satisfaisabilité ont également d’autres applications en raison-

nement automatique, vision par ordinateur, bases de données, robotique, conception
assistée par ordinateur. Gu, Purdom, Franco et Wah ont écrit un article de synthèse
[GU 97] citant de nombreuses applications de problèmes de satisfaisabilité (environ
250 références).

Face à un problème de satisfaisabilité, on peut soit l’étudier du point de vue théo-

rique (établir sa complexité exacte ou d’approximation, bâtir des algorithmes qui ga-
rantissent une solution exacte ou approchée), soit le résoudre du point de vue pratique.
Parmi les méthodes les plus efficaces pour la résolution pratique des problèmes de sa-
tisfaisabilité citons : la recherche locale, la recherche tabou, le recuit simulé. Pour plus
de détails, on pourra se reporter à [GU 97] et [GEN 99] qui proposent une synthèse de
la plupart des algorithmes pratiques de résolution pour les problèmes de satisfaisabi-
lité.
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 3

Dans ce chapitre, nous présentons les principaux résultats de complexité exacte et

d’approximation pour les problèmes de satisfaisabilité selon le type de fonctions boo-
léennes intervenant dans les contraintes. Notre but n’est pas de présenter de manière
exhaustive tous les résultats existant dans la littérature mais d’identifier les problèmes
les plus étudiés et d’introduire les concepts et algorithmes de base. La plupart des
problèmes de satisfaisabilité sont difficiles. Il est donc intéressant, à la fois du point
de vue théorique et pratique, d’identifier des cas particuliers qui sont plus faciles.
Nous avons choisi de présenter les cas particuliers les plus étudiés : les instances pla-
naires, les instances avec un nombre borné d’occurrences de chaque variable et les
instances denses. Plusieurs problèmes d’optimisation se modélisent comme un pro-
blème de satisfaisabilité avec une contrainte globale additionnelle sur l’ensemble des
solutions réalisables. En particulier, le problème M IN B ISECTION, dont la complexité
d’approximation n’est toujours pas établie, se modélise comme un problème de sa-
tisfaisabilité où l’ensemble des solutions réalisables est l’ensemble des assignations
équilibrées (avec autant de variables fixées à 0 que à 1). Nous présentons également
quelques résultats obtenus sur les problèmes de satisfaisabilité sous cette contrainte
globale.

Pour le lecteur souhaitant approfondir la complexité des problèmes de satisfaisabi-

lité, citons dans la littérature, la monographie de Creignou, Khanna et Sudan [CRE 01]
où on peut trouver les preuves de la plupart des résultats importants dans ce domaine
et qui couvre en dehors des résultats présentés ici, d’autres aspects comme la com-
plexité de comptage, la complexité de représentation des fonctions ainsi que d’autres
problèmes de satisfaisabilité. Notons également l’existence d’un compendium élec-
tronique, de Crescenzi et Kann [CRE 95b], qui regroupe les résultats connus de com-
plexité d’approximation pour les problèmes d’optimisation, en particulier pour les
problèmes de satisfaisabilité.

Le chapitre est structuré comme suit. Dans la Section 1.2 nous introduisons les
types de fonctions booléennes que nous allons utiliser et définissons les problèmes de
décision et d’optimisation considérés. Dans la Section 1.3 nous étudions les problèmes
de décision et dans la Section 1.4 les problèmes de maximisation et minimisation.
Nous considérons ensuite quelques instances particulières des problèmes de satisfai-
sabilité : instances planaires (Section 1.5.1), denses (Section 1.5.2), avec un nombre
borné d’occurrences de chaque variable (Section 1.5.3). Nous présentons également
la complexité des problèmes de satisfaisabilité quand l’ensemble des solutions réa-
lisables est restreint aux assignations équilibrées (Section 1.6). Nous clôturons notre
chapitre par une brève conclusion (Section 1.7).

1.2. Préliminaires

Une instance d’un problème de satisfaction de contraintes booléennes est un en-

semble de m contraintes C1 , . . . , Cm définies sur un ensemble de n variables x1 , . . . , xn .
4 Optimisation Combinatoire

Une contrainte Cj est l’application d’une fonction booléenne f : {0, 1}k → {0, 1} à
un sous-ensemble de variables xi1 , . . . , xik où i1 , . . . , ik ∈ {1, . . . , n}. Cette contrainte
est également notée f (xi1 , . . . , xik ). Une assignation xi = vi , pour i = 1, . . . , n, où
vi ∈ {0, 1} satisfait la contrainte f (xi1 , . . . , xik ) si et seulement si f (vi1 , . . . , vik ) =
1.

Un littéral est une variable xi (littéral positif) ou bien sa négation x̄i (littéral néga-
tif).
E XEMPLE 1.1.– Quelques exemples de fonctions booléennes utilisées pour définir des
contraintes :
– T (x) = x, F (x) = x̄
– ORki (x1 , . . . , xk ) = x̄1 ∨ . . . ∨ x̄i ∨ xi+1 ∨ . . . ∨ xk , où i ≤ k représente le
nombre de littéraux négatifs dans la disjonction
– ANDki (x1 , . . . , xk ) = x̄1 ∧ . . . ∧ x̄i ∧ xi+1 ∧ . . . ∧ xk , où i ≤ k représente le
nombre de littéraux négatifs dans la conjonction
– XORk (x1 , . . . , xk ) = x1 ⊕ . . . ⊕ xk où ⊕ représente l’opérateur "ou exclusif"
(0 ⊕ 0 = 0, 1 ⊕ 0 = 1, 0 ⊕ 1 = 1, 1 ⊕ 1 = 0)
– XNORk (x1 , . . . , xk ) = x1 ⊕ . . . ⊕ xk

Une contrainte peut également se représenter comme une formule booléenne qui
peut avoir diverses formes. Une formule est sous forme normale conjonctive (CNF) si
elle est de la forme c1 ∧ . . . ∧ cm où chaque ct est une clause disjonctive, c’est-à-dire
de la forme ℓt1 ∨ . . . ∨ ℓtp où ℓti , i = 1, . . . , p sont des littéraux. Une formule est sous
forme normale disjonctive (DNF) si elle est de la forme c1 ∨ . . . ∨ cm où chaque ct est
une clause conjonctive, c’est-à-dire de la forme ℓt1 ∧ . . . ∧ ℓtp où ℓti , i = 1, . . . , p sont
des littéraux. Une formule kCNF (ou kDNF) est une formule CNF (ou DNF) dont
chaque clause contient au plus k littéraux.

Observons que si chaque contrainte d’un problème de satisfaisabilité est repré-

sentée par une formule CNF, l’ensemble des contraintes du problème est lui-même
représentable par une formule CNF correspondant à la conjonction des formules pré-
cédentes.

On distingue différents problèmes de satisfaisabilité selon le type de fonctions

booléennes utilisées pour définir les contraintes. Soit F un ensemble fini de fonc-
tions booléennes. Un F -ensemble de contraintes est un ensemble de contraintes qui
n’utilisent que des fonctions booléennes appartenant à F . Une assignation satisfait
un F -ensemble de contraintes si et seulement si elle satisfait chaque contrainte de
l’ensemble de contraintes.
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 5

1.2.1. Problèmes de satisfaction de contraintes : versions décision et optimisation

Nous définissons dans cette partie les classes de problèmes que nous allons étudier.
Il s’agit des versions décision et optimisation des problèmes de satisfaisabilité.

La version de décision d’un problème consiste à déterminer si ce problème admet

au moins une solution ; sa version recherche consiste à trouver une solution s’il en
existe. La version optimisation d’un problème consiste à chercher une solution qui
maximise ou minimise une fonction adéquate.

D ÉFINITION 1.1.– Le problème de satisfaisabilité SAT(F ) consiste à décider s’il

existe une assignation qui satisfait un F -ensemble de constraintes. Le problème de
recherche associé au problème de décision SAT(F ) consiste à trouver une assignation
qui satisfait un F -ensemble de constraintes si une telle assignation existe ou bien
répondre "non" sinon.

Dans ce chapitre nous allons voir qu’à chaque fois qu’on peut résoudre le problème
de décision SAT(F ) en temps polynomial, on peut également trouver une solution
pour les instances satisfaisables et donc résoudre le problème de recherche associé en
temps polynomial.

Il est usuel de distinguer certaines variantes de SAT(F ) où chaque fonction de F

dépend d’au plus (ou d’exactement) k variables. Ces variantes sont notées kSAT(F )
(ou EkSAT(F )).

Nous présentons ensuite quelque problèmes classiques de décision ainsi que le

problème de satisfaisabilité SAT(F ) correspondant :
– S AT est le problème consistant à décider si un ensemble de clauses disjonc-
tives définies sur n variables booléennes est satisfaisable. Il correspond au problème
SAT(F ) où F est l’ensemble des fonctions ORki , pour k ≤ n.
– C ONJ est le problème consistant à décider si un ensemble de clauses conjonc-
tives définies sur n variables booléennes est satisfaisable. Il correspond au problème
SAT(F ) où F est l’ensemble des fonctions ANDki , pour k ≤ n.
– L IN 2 est le problème consistant à décider si un ensemble d’équations linéaires
définies sur n variables booléennes est satisfaisable. Il correspond au problème
SAT(F ) où F est l’ensemble des fonctions XORk , XNORk , pour k ≤ n.
– 2S AT est la version de S AT où chaque clause disjonctive comporte au plus 2
littéraux, et il correspond à 2SAT(F ) où F est l’ensemble des fonctions ORki , pour
k ≤ 2.
– E3S AT est la version de S AT où chaque clause disjonctive a exactement 3 litté-
raux, et il correspond à SAT({OR30 , OR31 , OR32 , OR33 }).
6 Optimisation Combinatoire

D ÉFINITION 1.2.– Le problème de maximisation M AX SAT(F ) consiste à déterminer

une assignation qui satisfait un nombre maximum de contraintes d’un F -ensemble de
contraintes.

Par exemple, le problème M AX C UT, qui consiste à partitioner l’ensemble des

sommets d’un graphe en deux parties telles que le nombre d’arêtes dont les extrémités
appartiennent à des parties différentes soit maximum, peut se formuler comme un pro-
blème de type M AX SAT({XOR2 }) comme suit. Considérant un graphe G, instance
de M AX C UT, on associe à chaque sommet i une variable xi et à chaque arête (i, j)
de G la contrainte XOR2 (xi , xj ).

D ÉFINITION 1.3.– Le problème de minimisation M IN SAT D ELETION (F ) consiste à

déterminer une assignation qui minimise le nombre de contraintes non satisfaites d’un
F -ensemble de contraintes, ce qui correspond au nombre minimum de contraintes à
enlever tel que les contraintes restantes sont satisfaites.

M IN SAT D ELETION (F ) permet de modéliser naturellement certains problèmes

de minimisation. Par exemple, le problème s-t M IN C UT dans un graphe non-orienté,
qui consiste à partitioner l’ensemble des sommets d’un graphe en deux parties telles
que s et t appartiennent à des parties différentes et telles que le nombre d’arêtes dont
les extrémités appartiennent à des parties différentes soit minimum, peut se formuler
comme un problème de type M IN SAT D ELETION ({XNOR2 } ∪ {T, F }) comme suit.
Considérant un graphe G, instance de s-t M IN C UT, on associe à chaque sommet i
une variable xi et à chaque arête (i, j) de G la contrainte XNOR2 (xi , xj ). De plus on
ajoute les contraintes T (xs ) et F (xt ).
R EMARQUE 1.–
1) Les problèmes M AX SAT(F ) et M IN SAT D ELETION (F ) sont clairement re-
liés. En effet, considérant une instance I de M AX SAT(F ) avec m contraintes, une
solution optimale pour l’instance I de M AX SAT(F ) de valeur optMaxSAT (F ) (I)
est également une solution optimale de l’instance I du problème M IN SAT
D ELETION (F ) de valeur optMinSAT Deletion(F ) (I)= m-optMaxSAT (F ) (I). Ainsi, les
complexités exactes de M AX SAT(F ) et M IN SAT D ELETION (F ) coïncident. En
revanche, les complexités d’approximation des deux problèmes peuvent être très dif-
férentes comme nous allons le voir par la suite.
2) Dans la littérature, on définit également le problème M IN SAT(F ) qui consiste
à determiner une assignation minimisant le nombre de contraintes satisfaites. Par
exemple, dans le compendium de Crescenzi et Kann [CRE 95b], le problème M IN
S AT consiste à déterminer une assignation minimisant le nombre de clauses satis-
faites d’un ensemble de clauses disjonctives. Observons que M IN SAT(F ) est équi-
valent du point de vue exact et approximation) à M IN SAT D ELETION (F ′ ), où
F ′ est l’ensemble des fonctions complémentaires aux fonctions de F . Par exemple,
trouver une assignation qui minimise le nombre de contraintes satisfaites parmi les
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 7

contraintes x1 ∨ x2 , x1 ∨ x̄3 , x2 ∨ x3 , x̄1 ∨ x̄2 est équivalent à trouver une assi-

gnation qui minimise le nombre de contraintes non satisfaites parmi les contraintes
x̄1 ∧ x̄2 , x̄1 ∧ x3 , x̄2 ∧ x̄3 , x1 ∧ x2 . Ainsi le problème M IN S AT est équivalent à M IN
SAT D ELETION (F ) où les contraintes sont des clauses conjonctives (problème appelé
dans la suite M IN C ONJ D ELETION). Dans la suite, nous considérons uniquement le
problème M IN SAT D ELETION (F ).

1.2.2. Types de contraintes

La complexité de SAT(F ) ainsi que les complexités exactes et d’approximation

de M AX SAT(F ) et M IN SAT D ELETION (F ) dépendent des types des fonctions
booléennes de l’ensemble F . Dans cette partie, nous décrivons les types de fonctions
booléennes qui ont été les plus étudiées et dont nous allons discuter dans la suite du
chapitre.

Une fonction booléenne f est :

– 0-valide si f (0, . . . , 0) = 1
– 1-valide si f (1, . . . , 1) = 1
– Horn si elle peut s’exprimer comme une formule CNF ayant au plus un littéral
positif dans chaque clause
– anti-Horn si elle peut s’exprimer comme une formule CNF ayant au plus un
littéral négatif dans chaque clause
– affine si elle peut s’exprimer comme une conjonction d’équations linéaires sur
le corp de Galois GF (2), c’est-à-dire comme une conjonction d’équations de type
xi1 ⊕ . . . ⊕ xip = 0 ou xj1 ⊕ . . . ⊕ xjq = 1.
– bijonctive si elle peut s’exprimer comme une formule 2CNF
– 2-monotone si elle peut s’exprimer comme une formule DNF de la forme xi1 ∧
. . . ∧ xip ou x̄ℓ1 ∧ . . . ∧ x̄ℓq ou (xi1 ∧ . . . ∧ xip ) ∨ (x̄ℓ1 ∧ . . . ∧ x̄ℓq ). Remarquons
qu’une fonction 2-monotone est à la fois Horn et anti-Horn.
– fermée au complément si pour toute assignation v on a f (v) = f (v̄), où v̄ est
l’assignation complémentaire à v

On étend les notions précédentes à un ensemble F de fonctions dès lors que toutes
les fonctions de F ont la propriété requise. Par exemple, si chaque fonction de F est
Horn alors l’ensemble F est Horn et le problème SAT(F ) est appelé H ORN S AT.
Les formules Horn interviennent en intelligence artificielle pour déveloper des sys-
tèmes experts ou formaliser des bases de connaissances. Elle représentent également
le fondement logique de Prolog.

La notation utilisée dans la littérature pour le problème SAT(F ) quand F est affine
est L IN 2. k-L IN 2 est le problème kSAT(F ) où F est affine et Ek-L IN 2 est la variante
8 Optimisation Combinatoire

de k-L IN 2 où chaque équation dépend exactement de k variables. Une instance de

L IN 2 est 0-homogène (respectivement 1-homogène) si toutes ses équations linéaires
ont leur termes libres égaux à 0 (respectivement 1).

M ONOTONE -S AT et M ONOTONE -kS AT sont les variantes de S AT et kS AT où toute

clause ne contient que des littéraux positifs ou toute clause ne contient que des litté-
raux négatifs.

Nous allons considérer dans ce chapitre d’autres variantes de SAT(F ) :

– le problème NAE3S AT est S AT ({f }), où f est d’arité 3 et f (x1 , x2 , x3 ) = 1 si
et seulement si les 3 variables n’ont pas la même valeur, plus précisément, f (0, 0, 0) =
f (1, 1, 1) = 0 sinon f prend la valeur 1.
– le problème 1 IN 3S AT est S AT ({g}), où g est d’arité 3 et g(x1 , x2 , x3 ) = 1
si et seulement si exactement une des 3 variables a la valeur 1, plus précisément,
g(1, 0, 0) = g(0, 1, 0) = g(0, 0, 1) = 1, sinon g prend la valeur 0.
R EMARQUE 2.– Pour certaines variantes du problème SAT(F ), l’ensemble des contraintes
peut être représenté de façon équivalent par une formule mettant en conjonction ces
contraintes. Dans les problèmes d’optimisation correspondants M AX SAT(F ) et M IN
SAT D ELETION (F ), nous n’utilisons que la formulation sous forme d’un ensemble
de contraintes afin de pouvoir compter le nombre de contraintes satisfaites.

Nous présentons ensuite quelques variantes de problèmes d’optimisation utilisées

dans la suite du chapitre :
– M AX S AT, consiste, étant donné un ensemble de clauses disjonctives définies sur
n variables booléennes, à trouver une assignation maximisant le nombre de clauses sa-
tisfaites. M AX S AT correspond donc au problème M AX SAT(F ) où F est l’ensemble
des fonctions ORki , pour k ≤ n.
– M IN S AT D ELETION, consiste, étant donné un ensemble de clauses disjonctives
définies sur n variables booléennes, à trouver une assignation minimisant le nombre
de clauses non satisfaites. M IN S AT D ELETION correspond donc au problème M IN
SAT D ELETION (F ) où F est l’ensemble des fonctions ORki , pour k ≤ n.
– M AX C ONJ, consiste, étant donné un ensemble de clauses conjonctives défi-
nies sur n variables booléennes, à trouver une assignation maximisant le nombre de
clauses satisfaites. M AX C ONJ correspond donc au problème M AX SAT(F ) où F est
l’ensemble des fonctions ANDki , pour k ≤ n.
– M IN C ONJ D ELETION, consiste, étant donné un ensemble de clauses conjonc-
tives définies sur n variables booléennes, à trouver une assignation minimisant le
nombre de clauses non satisfaites. M IN C ONJ D ELETION correspond donc au pro-
blème M IN SAT D ELETION (F ) où F est l’ensemble des fonctions ANDki , pour
k ≤ n.
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 9

– M AX L IN 2, consiste, étant donné un ensemble d’équations linéaires définies sur

n variables booléennes, à trouver une assignation maximisant le nombre d’équations
satisfaites. M AX L IN 2 correspond donc au problème M AX SAT(F ) où F est l’en-
semble des fonctions XORk , XNORk , pour k ≤ n.
– M IN L IN 2 D ELETION, consiste, étant donné un ensemble d’équations linéaires
définies sur n variables booléennes, à trouver une assignation minimisant le nombre
d’équations non satisfaites. M IN L IN 2 D ELETION correspond donc au problème M IN
SAT D ELETION (F ) où F est l’ensemble des fonctions XORk , XNORk , pour k ≤ n.
– Les problèmes M AX kS AT, M AX EkS AT, M AX kC ONJ, M AX EkC ONJ, M AX
k-L IN 2, M AX Ek-L IN 2 ainsi que les versions M IN D ELETION correspondantes sont
définis de manière similaire sur des clauses ou équations de taille (au plus) k.

1.3. Complexité des problèmes de décision

Nous étudions dans cette section la complexité des problèmes de décision SAT(F )
selon le type de fonctions de l’ensemble F .

S AT est le premier problème montré NP-complet par Cook [COO 71] et Levin
[LEV 73]. On peut réduire facilement S AT à kS AT, k ≥ 3 ce qui implique la NP-
complétude de kS AT, pour k ≥ 3. Par contre, 2S AT est polynomial [COO 71].

T HÉORÈME 1.1.– 2S AT est résoluble en temps polynomial.

Preuve : Soit I une instance de 2S AT avec m clauses C1 , . . . , Cm et n variables

x1 , . . . , xn . Nous allons construire un graphe orienté GI avec 2n sommets v1 , v̄1 ,. . . ,
vn , v̄n , où vi (resp. v̄i ) correspond à xi (resp. x̄i ). Pour un littéral ℓi (resp. ℓ̄i ), notons
par wi (resp. w̄i ) le sommet correspondant. Ainsi, si ℓi = xi alors wi = vi et w̄i = v̄i
et si ℓi = x̄i alors wi = v̄i et w̄i = vi . Chaque clause constituée d’un seul littéral ℓ
est remplacée par la clause équivalente ℓ ∨ ℓ. Pour chaque clause ℓ1 ∨ ℓ2 , équivalente
aux implications logiques ℓ̄1 ⇒ ℓ2 et ℓ̄2 ⇒ ℓ1 , introduisons dans GI les arcs (w̄1 , w2 )
et (w̄2 , w1 ). Observons alors que si dans GI il existe un chemin de wi à wj alors il
existe aussi un chemin de w̄j à w̄i .

Considérons une assignation de valeurs de vérité pour les sommets de GI . Cette

assignation correspond à une assignation de x1 , . . . , xn satisfaisant I si et seulement
si :
(a) pour chaque i, vi et v̄i ont des valeurs complémentaires.
(b) aucun arc (wp , wq ) n’est tel que wp a la valeur 1 et wq a la valeur 0 (sinon
l’implication logique ℓp ⇒ ℓq serait fausse).

Nous allons justifier ensuite que I est satisfaisable si et seulement si dans GI , aucun
sommet vi n’est dans la même composante fortement connexe que v̄i .
10 Optimisation Combinatoire

Supposons que I est satisfaisable et qu’il existe un sommet vi appartenant à la

même composante fortement connexe que v̄i . Soit une assignation pour x1 , . . . , xn
satisfaisant I. Cette assignation induit une assignation des valeurs de vérité pour les
sommets de GI satisfaisant (a). Comme vi appartient à la même composante fortement
connexe que v̄i , il existe dans GI un chemin de vi à v̄i et de v̄i à vi . L’un de ces
deux chemins a nécessairement pour extrémité initiale un sommet évalué à 1 et pour
extrémité terminale un évalué à 0. Il contient donc un arc (wp , wq ) tel que wp a pour
valeur 1 et wq a pour valeur 0 ce qui contredit (b) et donc le fait que I soit satisfaisable.

Supposons maintenant qu’aucun sommet vi n’est dans la même composante for-

tement connexe que v̄i . Nous allons construire une assignation sur les sommets telles
que (a) et (b) sont satisfaites. Déterminons d’abord les composantes fortement connexes
de GI en utilisant l’algorithme linéaire de Tarjan [TAR 72]. Construisons ensuite
le graphe réduit de GI , noté GrI , dont les sommets sont les composantes fortement
connexes et où l’on crée un arc d’une composante S1 à une composante S2 s’il existe
un arc d’un sommet de S1 vers un sommet de S2 . Notons S̄i la composante fortement
connexe contenant les littéraux complémentaires aux littéraux de Si . Évidemment si
S1 est un prédécesseur de S2 alors S̄2 est un prédécesseur de S̄1 . L’algorithme de
Tarjan génère les composantes fortement connexes en ordre topologique inverse, plus
précisément si S1 est générée avant S2 , alors S1 ne peut être un prédécesseur de S2 .

Nous allons définir ensuite des valeurs de vérité pour les sommets de GrI ; un som-
met de GI aura alors la valeur de vérité de la composante à laquelle il appartient. Nous
répétons l’algorithme suivant tant que possible : considérons la première composante
S dans l’ordre topologique inverse, qui n’a pas de valeur de vérité et attribuons la va-
leur 1 à S et la valeur 0 à la composante S̄. Évidement (a) est satisfait. Pour justifier
que (b) est satisfait il faut montrer qu’il n’existe pas d’arc d’un sommet correspondant
à un littéral de valeur 1 vers un sommet correspondant à un littéral de valeur 0. S’il
existait un arc d’un sommet w1 de valeur 1 appartenant à la composante S1 vers un
sommet w2 de valeur 0 appartenant à la composante S2 alors dans GrI il existe un
arc de S1 (valuée 1) à S2 (valuée 0) et de S̄2 (valuée 1) à S̄1 (valuée 0). Cela contre-
dit la manière dont nous avons attribué les valeurs 1 aux composantes car dans un
ordre topologique inverse S2 est avant S1 et S̄1 est avant S̄2 et donc une au moins des
composantes S2 ou S̄1 devrait avoir la valeur 1. 

Tester la satisfaisabilité d’une formule Horn a été montré polynomial par Jones
et Laaser [JON 77] et la complexité de l’algorithme polynomial a été améliorée par
Dowling et Gallier [DOW 84] et Minoux [MIN 88].

T HÉORÈME 1.2.– H ORN S AT est resoluble en temps polynomial.

Preuve : Considérons une instance I de H ORN S AT. Si I ne contient pas de clause

unitaire, chaque clause contient au moins un littéral négatif et il suffit de fixer toutes
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 11

les variables à 0 pour obtenir une assignation satisfaisante. Si I contient au moins une
clause unitaire, on utilise le principe de résolution unitaire qui consiste à appliquer
itérativement les deux règles suivantes :
1) Si une clause est constituée d’un littéral positif xi (ou d’un littéral négatif x̄i ),
alors fixer xi à 1 (ou à 0) et supprimer la clause.
2) Tant qu’il existe une clause contenant au moins une variable fixée, alors la for-
mule peut être réduite ainsi :
(a) supprimer toute clause contenant un littéral positif xi où xi a été fixée à 1 (ou
un littéral négatif x̄i où xi a été fixée à 0) car cette clause va être automatiquement
satisfaite indépendamment des valeurs des autres littéraux de la clause.
(b) dans toute clause effacer tout littéral positif xi tel que xi a été fixée à 0 (ou
tout littéral négatif x̄i tel que xi a été fixée à 1) car un tel littéral ne va jamais satisfaire
cette clause.
Si en appliquant (b) on efface tous les littéraux d’une clause alors la formule
n’est pas satisfaisable.

Après avoir appliqué les règles 1 et 2, trois cas sont possibles :

– I est déclarée non satisfaisable en 2(b).
– I est satisfaisable car toutes ses clauses ont été supprimées par l’application de
1 et 2(a).
– l’assignation partielle obtenue définit une sous-instance I ′ qui ne contient pas
de clause unitaire. I est donc satisfaisable en fixant à 0 les variables non fixées par
l’assignation partielle.

Évidemment un algorithme semblable au précédent peut être établi pour décider

si SAT(F ) est satisfaisable quand F est anti-Horn et dans le cas positif trouver une
assignation satisfaisante. Chacun de ces deux algorithmes fonctionne également quand
F est 2-monotone.

Quad F est affine, SAT(F ) est également résoluble en temps polynomial en utili-
sant l’élimination de Gauss :

T HÉORÈME 1.3.– L IN 2 est résoluble en temps polynomial.

Donc SAT(F ) est résoluble en temps polynomial quand chaque fonction de F est
une clause disjonctive de taille au plus 2 (ou plus généralement quand chaque fonc-
tion de F est 2CNF), quand F est Horn ou anti-Horn et quand F est affine. Existe-t’il
d’autres cas particuliers pour lesquels SAT(F ) est résoluble en temps polynomial ?
Schaefer [SCH 78] a établi une caractérisation de la complexité des problèmes de dé-
cision en fonction du type de contraintes, qui montre que les seuls cas où SAT(F ) est
12 Optimisation Combinatoire

résoluble en temps polynomial sont les cas précédents ainsi que le cas trivial où F est
0 ou 1-valide. Dans ce dernier cas, une des deux assignations triviales (l’assignation 0
pour chaque variable ou l’assignation 1 pour chaque variable) est une solution réali-
sable. Par exemple, M ONOTONE -S AT est résoluble en temps polynomial car il rentre
dans ce dernier cas.

T HÉORÈME 1.4.– [Théorème dichotomique pour SAT(F ) [SCH 78]]

Étant donné un F -ensemble de contraintes, le problème SAT(F ) est dans P si F
satisfait une des conditions suivantes, et SAT(F ) est NP-complet autrement.
– F est 0-valide (1-valide)
– F est Horn (anti-Horn)
– F est affine
– F est bijonctive

1.4. Complexité et approximation des problèmes d’optimisation

Dans cette section nous présentons d’abord un algorithme polynomial pour ré-
soudre M AX SAT(F ) quand F est 2-monotone. Ensuite, nous mettons en évidence
quelques méthodes classiques qui permettent d’établir des résultats positifs d’approxi-
mation pour M AX SAT(F ). Nous citons également d’autres résultats positifs et néga-
tifs existant dans la littérature sur M AX SAT(F ) et M IN SAT D ELETION (F ).

1.4.1. Problèmes de maximisation

Si un problème SAT(F ) est NP-difficile alors le problème M AX SAT(F ) corres-

pondant est aussi NP-difficile. Cependant, il existe des problèmes de maximisation
qui deviennent difficiles même si les problèmes de décision correspondants sont fa-
ciles. Ainsi, M AX 2S AT est NP-difficile [GAR 74], M AX H ORN S AT est NP-difficile
[KOH 94] même si 2S AT et H ORN S AT admettent des algorithmes polynomiaux.
Néanmoins, dans certains cas, M AX SAT(F ) est polynomial. Un premier cas trivial
est celui où F est 0 ou 1-valide, toutes les contraintes étant alors nécessairement sa-
tisfaites.

Nous avons vu dans la section précédente que SAT(F ) est polynomial quand F
est 2-monotone (en utilisant l’algorithme pour F Horn ou anti-Horn). En fait, on peut
établir un résultat plus fort qui permet de déterminer en temps polynomial une assi-
gnation maximisant le nombre de contraintes satisfaites.

T HÉORÈME 1.5.– [Creignou [CRE 95a], Khanna, Sudan, Williamson [KHA 97b]]
M AX SAT(F ) est polynomial quand chaque fonction de F est une fonction 2-monotone.
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 13

Preuve : On considère le problème équivalent M IN SAT D ELETION (F ) que l’on

réduit au problème s-t M IN C UT dans un graphe orienté. Considérons une instance I
du problème M AX SAT(F ) sur n variables et avec m contraintes, chaque fonction de
F étant une fonction 2-monotone de type
1) xi1 ∧ . . . ∧ xip
2) x̄ℓ1 ∧ . . . ∧ x̄ℓq
3) (xi1 ∧ . . . ∧ xip ) ∨ (x̄ℓ1 ∧ . . . ∧ x̄ℓq )

On construit un graphe orienté GI = (V, A) où V contient 2 sommets spéciaux F , T ,

un sommet xi pour chacune des n variables xi et un sommet vj pour une contrainte
Cj de type 1, un sommet v̄j pour une contrainte Cj de type 2 et deux sommets vj et
v̄j pour une contrainte Cj de type 3. Pour construire l’ensemble des arcs on procède
comme suit :
– pour une contrainte Cj de type 1, on crée un arc de coût ∞ de xik à vj pour
k = 1, . . . , p et un arc de coût 1 de vj à T .
– pour une contrainte Cj de type 2, on crée un arc de coût ∞ de v̄j à xℓk pour
k = 1, . . . , q et un arc de coût 1 de F à v̄j .
– pour une contrainte Cj de type 3, on crée un arc de coût ∞ de xik à vj pour
k = 1, . . . , p, un arc de coût ∞ de v̄j à xℓk pour k = 1, . . . , q et un arc de coût 1 de
vj à v̄j .

Nous justifions ensuite que la valeur d’une coupe minimale de F à T correspond

à une assignation avec un nombre minimum de contraintes non satisfaites. Rappelons
que la valeur d’une coupe engendrée par une partition (A, B) avec F ∈ A et T ∈ B
est la somme des coûts des arcs dont l’extrémité initiale appartient à A et l’extrémité
terminale appartient à B.

Étant donnée une coupe C ∗ de valeur minimale de F à T , considérons l’assi-

gnation qui attribue 0 (respectivement 1) aux variables qui se trouvent dans la même
partie que F (respectivement T ). Si un arc de coût 1 de vj à T , correspondant à une
contrainte de type 1, fait partie de la coupe C ∗ , alors au moins une des variables
xi1 , . . . , xip est fixée à 0 car sinon les sommets correspondant à ces variables sont
tous dans la même partie que T dans la coupe C ∗ et alors en mettant vj du coté T de
la coupe on obtiendrait une coupe de valeur inférieure à la valeur de la coupe C ∗ , ce
qui contredit le fait que C ∗ est une coupe de valeur minimale. Ainsi la contrainte Cj
n’est pas satisfaite. De la même manière on peut justifier que si un arc de coût 1 de
F à v̄j , correspondant à une contrainte de type 2, fait partie de la coupe C ∗ , alors la
contrainte Cj correspondante n’est pas satisfaite. De plus, si un arc de coût 1 de vj à
v̄j , correspondant à une contrainte de type 3, fait partie de la coupe C ∗ , alors au moins
une parmi les variables xi1 , . . . , xip est fixée à 0 et au moins une parmi les variables
xℓ1 , . . . , xℓq est fixée à 1 et donc la contrainte Cj correspondante n’est pas satisfaite.
14 Optimisation Combinatoire

Considérons maintenant une assignation pour x1 , . . . , xn qui minimise le nombre

de contraintes non satisfaites. La valeur de la coupe suivante est égale au nombre de
contraintes non satisfaites par l’assignation précédente :
– placer les sommets correspondant aux variables fixées à 0 (respectivement 1)
dans cette assignation dans la même partie que F (respectivement T ).
– placer le sommet vj correspondant à une contrainte Cj de type 1 dans la partie
de T (ou F ) si Cj est satisfaite (ou non satisfaite).
– placer le sommet v̄j correspondant à une contrainte Cj de type 2 dans la partie
de F (ou T ) si Cj est satisfaite (ou non satisfaite).
– si Cj est une contrainte de type 3, si xi1 ∧ . . . ∧ xip est satisfaite mettre vj dans
la partie de T sinon dans la partie de F et si x̄ℓ1 ∧ . . . ∧ x̄ℓq est satisfaite placer v̄j dans
la partie de F sinon dans la partie de T .

Ainsi, M AX SAT(F ) est résoluble en temps polynomial quand chaque fonction

de F est une fonction 0-valide, 1-valide ou 2-monotone. Le théorème de classification
pour M AX SAT(F ) établit que les cas précédents sont les seuls cas pour lesquels le
problème est facile.

T HÉORÈME 1.6.– [Théorème de classification pour M AX SAT(F ) [CRE 95a, KHA 97b]]
M AX SAT(F ) est dans P si F est 0-valide ou 1-valide ou 2-monotone et M AX
SAT(F ) est APX-complet autrement.

Dans la suite nous allons établir quelques algorithmes d’approximation pour un

problème difficile, M AX S AT. Un premier algorithme d’approximation très simple a
été proposé par Johnson [JOH 74].
1
T HÉORÈME 1.7.– [JOH 74] M AX S AT est approximable à un facteur 2 près.

Preuve : Considérons une instance avec m clauses C1 , . . . , Cm sur n variables x1 , . . . , xn ,

dont la valeur optimale est noté opt. L’algorithme consiste, pour chaque variable xi ,
à considérer xi = 1 avec la probabilité 12 et xi = 0 avec la probabilité 12 . Cet algo-
rithme fournit une approximation à un facteur 21 près. Soit W la variable aléatoire qui
représente le nombre de clauses satisfaites, alors l’espérance de cette variable aléatoire
est :
m m
X X 1 m opt
E(W ) = P (Cj est satisfaite) = (1 − |C | ) ≥ ≥ .
j=1 j=1
2 j 2 2

En utilisant la méthode de l’espérance conditionnelle proposée par Erdös et Sel-

fridge [ERD 73], on peut transformer cet algorithme en un algorithme déterministe
avec la même garantie de performance comme suit :
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 15

Nous allons fixer des valeurs aux variables dans l’ordre x1 , . . . , xn . Supposons
qu’on a fixé les valeurs b1 , . . . , bi aux variables x1 , . . . , xi . Calculons E(W |x1 =
b1 , . . . , xi = bi , xi+1 = 0) et E(W |x1 = b1 , . . . , xi = bi , xi+1 = 1) et soit xi+1 = 0
si E(W |x1 = b1 , . . . , xi = bi , xi+1 = 0) ≥ E(W |x1 = b1 , . . . , xi = bi , xi+1 = 1)
et xi+1 = 1 sinon. Comme
1
E(W |x1 = b1 , . . . , xi = bi ) = E(W |x1 = b1 , . . . , xi = bi , xi+1 = 1)+
2
1
E(W |x1 = b1 , . . . , xi = bi , xi+1 = 0)
2
alors
max{E(W |x1 = b1 , . . . , xi = bi , xi+1 = 1), E(W |x1 = b1 , . . . , xi = bi , xi+1 = 0)} ≥
E(W |x1 = b1 , . . . , xi = bi )

L’assignation trouvée à la fin x1 = b1 , . . . , xn = bn a la valeur égale à

opt
E(W |x1 = b1 , . . . , xn = bn ) ≥ E(W ) ≥ .
2


En utilisant la méthode de l’arrondi aléatoire, Goemans, Williamson [GOE 94] ont

amélioré le résultat précédent.

T HÉORÈME 1.8.– [GOE 94] M AX S AT est approximable à un facteur 1 − 1e ≈ 0, 632

près.

Preuve : Soit I une instance de M AX S AT avec m clauses C1 , . . . , Cm sur n variables

x1 , . . . , xn . L’algorithme est le suivant :
1) Formuler M AX S AT comme un programme linéaire en variables 0-1. On associe
à chaque variable booléenne xi une variables 0-1 yi et à chaque clause Cj une variable
zj telle que zj va prendre la valeur 1 si et seulement si Cj est satisfaite. Soit Cj+ =
{i : xi ∈ Cj } et Cj− = {i : x̄i ∈ Cj }. Alors le programme linéaire associé à M AX
S AT est :
Pm
 max j=1 zjP

P
(Sat) i∈Cj yi +
+
i∈Cj− (1 − yi ) ≥ zj (j = 1, . . . , m)

yi ∈ {0, 1} (i = 1, . . . , n), zj ∈ {0, 1} (j = 1, . . . , m)
2) Résoudre le problème relaxé (P).
Pm
 max j=1 zjP

P
+ yi +
(P ) i∈Cj i∈Cj− (1 − yi ) ≥ zj (j = 1, . . . , m)

yi ∈ [0, 1] (i = 1, . . . , n), zj ∈ [0, 1] (j = 1, . . . , m)
Soit (y ∗ , z ∗ ) la solution optimale trouvée.
16 Optimisation Combinatoire

3) Considérons l’assignation : xi = 1 avec la probabilité yi∗ et xi = 0 avec la

probabilité 1 − yi∗ .

Soit W la variable aléatoire qui représente le nombre de clauses satisfaites. Alors

l’espérance de cette variable aléatoire est :
m
X m
X
E(W ) = P (Cj est satisfaite) = (1 − Πi∈C + (1 − yi∗ )Πi∈C − yi∗ )
j j
j=1 j=1

Nous allons montrer que 1 − Πi∈C + (1 − yi∗ )Πi∈C − yi∗ ≥ (1 − 1e )zj∗ .

j j

Pour cela, montrons d’abord que pour toute solution (y, z) de (P) et toute clause
Cj avec k littéraux, on a

1 − Πi∈C + (1 − yi )Πi∈C − yi ≥ ck zj ,
j j

où ck = 1 − (1 − k1 )k .

Dans (Sat), l’inégalité correspondant à Cj est :

X X
yi + (1 − yi ) ≥ zj ⇐⇒
i∈Cj+ i∈Cj−

X X
|Cj+ | + |Cj− | − yi − (1 − yi ) ≤ k − zj ⇐⇒
i∈Cj+ i∈Cj−
X X
(1 − yi ) + yi ≤ k − zj .
i∈Cj+ i∈Cj−

a1 +...+ak √
Sachant que l’on a l’inégalité classique k ≥ k a1 . . . an , ∀a1 , . . . , ak ≥ 0,
on a
P P !k
i∈Cj+ (1 − yi ) + i∈Cj− yi
1 − Πi∈C + (1 − yi )Πi∈C − yi ≥ 1 −
j j k
 k
k − zj  zj k
≥1− =1− 1−
k k

Considérons la fonction f (x) = 1 − (1 − kx )k . On peut vérifier facilement que f

est concave, f (0) = 0 et f (1) = 1 − (1 − k1 )k = ck . Sachant que si f est concave,
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 17

alors pour montrer que f (x) ≥ ax + b, pour x ∈ [u, v], il est suffisant de montrer que
f (u) ≥ au + b et f (v) ≥ av + b, on en déduit que f (x) ≥ ck x, pour x ∈ [0, 1].

Ainsi,
 zj k
1 − Πi∈C + (1 − yi )Πi∈C − yi ≥ 1 − 1 − ≥ ck z j
j j k

Comme c1 (= 1) > c2 (= 34 ) > . . . > ck > . . . > 1 − 1e , on a :

1
1 − Πi∈C + (1 − yi∗ )Πi∈C − yi∗ ≥ (1 − )zj∗
j j e
pour tout j = 1, . . . , m.

Ainsi, nous obtenons finalement

m
X 1 1 1
E(W ) ≥ (1 − )zj∗ = (1 − )optP ≥ (1 − )optSat .
j=1
e e e

En utilisant la méthode de l’espérance conditionnelle proposée par Erdös et Sel-

fridge [ERD 73], on peut transformer cet algorithme en un algorithme déterministe
avec la même garantie de performance comme dans le Théorème 1.7. 

Goemans et Williamson [GOE 94] ont amélioré ensuite l’algorithme précédent

pour M AX S AT.
3
T HÉORÈME 1.9.– [GOE 94] M AX S AT est approximable à un facteur 4 près.

Preuve : L’algorithme consiste à attribuer à un bit b la valeur 0 avec la probabilité 12

et la valeur 1 avec la probabilité 12 . Si b = 0 on applique l’algorithme de Johnson et si
b = 1 on applique l’algorithme de l’arrondi aléatoire précédent.

Pour une clause Cj de taille k, soit Wj la variable aléatoire qui indique si la clause
est satisfaite.
1
E(Wj ) = [E(Wj |b = 0) + E(Wj |b = 1)]
2
1 1
E(Wj |b = 0) = 1 − k ≥ (1 − k )zj∗
2 2
1 1
E(Wj |b = 1) = 1 − (1 − )k ≥ (1 − (1 − )k )zj∗
k k
Donc, E(Wj ) ≥ 34 zj∗ et E(W ) = m 3
P
i=1 E(Wj ) ≥ 4 optSat .
18 Optimisation Combinatoire

Utilisation de la méthode de l’espérance conditionnelle permet de retrouver un

algorithme déterministe avec la même garantie de performance. 

Le résultat précédent n’est pas le meilleur connu dans la littérature concernant

l’approximation de M AX S AT. Asano et Williamson [ASA 00] ont établi un algo-
rithme d’approximation à un facteur 0,784 près pour M AX S AT. L’algorithme de
Johnson pour M AX S AT [JOH 74] établit également une approximation à un facteur
2k −1
2k
près pour M AX EkS AT, k ≥ 2. Une autre méthode qui a permis d’obtenir de
meilleurs résultats d’approximation pour M AX S AT et ses variantes consiste à mo-
déliser le problème comme un programme semi-défini et d’utiliser l’arrondi aléatoire
[GOE 95]. Ainsi, en suivant cette méthode pour la version M AX 2S AT, Feige et Goe-
mans [FEI 95] ont obtenu le meilleur algorithme d’approximation qui donne une ap-
proximation à 0,931 près. Du coté négatif, Papadimitriou et Yannakakis [PAP 88] ont
montré que M AX kS AT, k ≥ 2 est MAX SNP-difficile, ce qui implique qu’il n’a pas
de schéma d’approximation en temps polynomial. Ultérieurement, Håstad [HÅS 97] a
montré que même la version M AX EkS AT, k ≥ 3, n’est pas approximable à un facteur
k
( 2 2−1
k − ε) près, pour tout ε > 0 et que M AX E2S AT n’est pas approximable à un
facteur ( 21
22 − ε) près, pour tout ε > 0, si P6=NP.

En utilisant également la relaxation de la programmation entière et l’arrondi aléa-

toire, Trevisan [TRE 96] a montré que M AX kC ONJ, k ≥ 2, est approximable à un fac-
1
teur 2k−1 près. M AX C ONJ est aussi difficile à approximer que M AX I NDEPENDENT
1
S ET [CRE 96], c’est-à-dire qu’il n’est pas approximable à un facteur m1−ε près, pour
tout ε > 0 si NP6= ZPP, où m est le nombre de contraintes.

L’algorithme de Johnson pour M AX S AT [JOH 74] peut être appliqué également

pour M AX L IN 2 et M AX kL IN 2, k ≥ 2, fournissant une approximation à un facteur
1
2 près. Håstad [HÅS 97] a montré que même la version M AX E3L IN n’est pas ap-
proximable à un facteur ( 21 − ε) près, pour tout ε > 0 et que M AX E2L IN n’est pas
approximable à un facteur ( 11
12 − ε) près, pour tout ε > 0, si P6=NP.

1.4.2. Problèmes de minimisation

Considérons le problème M IN SAT D ELETION (F ). Compte tenu de l’équivalence

de ce problème avec M AX SAT(F ) du point de vue complexité exacte, les cas poly-
nomiaux pour M IN SAT D ELETION (F ) sont exactement les mêmes que pour M AX
SAT(F ), à savoir quand F est 0-valide, 1-valide et 2-monotone.

Considérons maintenant la complexité d’approximation. Un théorème de classi-

fication a été également établi pour M IN SAT D ELETION (F ) par Khanna, Sudan et
Trevisan [KHA 97a]. Ce théorème est beaucoup plus complexe que les théorèmes de
classification pour SAT(F ) et M AX SAT(F ).
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 19

Klauck [KLA 96] a montré que M IN 3S AT D ELETION n’est pas approximable à

un facteur n1−ε près, pour tout ε > 0 si P6= NP, où n est le nombre de variables. Par
contre, M IN 2S AT D ELETION est approximable à un facteur O(log n log log n) près
[KLE 97] et il n’a pas de schéma d’approximation.

M IN kC ONJ D ELETION, k ≥ 2, est approximable à un facteur 2(1 − 21k ) près

[BER 96], et MAX SNP-difficile [KOH 94] et donc il n’a pas de schéma d’approxima-
tion. M IN 2C ONJ D ELETION est approximable à un facteur de 1,103 près et il n’est
pas approximable à 67 − ε près pour tout ε > 0 si P6= NP et M IN 3C ONJ D ELETION
est approximable à un facteur de 1,213 près et il n’est pas approximable à 15
14 − ε
près pour tout ε > 0 si P6= NP [AVI 02]. M IN C ONJ D ELETION est aussi difficile à
approximer que M IN V ERTEX C OVER [CRE 96], c’est-à-dire qu’il est approximable
à un facteur 2 près et il n’a pas de schéma d’approximation.

Le problème M IN E2-L IN 2 D ELETION a été montré MAX SNP-difficile dans

[GAR 93] et n’admet donc pas de schéma d’approximation en temps polynomial. En
revanche, il est approximable à un facteur O(log n) près [GAR 93]. Les problèmes
M IN Ek-L IN 2 D ELETION sont extrêmement difficiles à approximer pour tout k ≥ 3.
En fait, ils ne sont pas approximables en temps polynomial à un facteur nΩ(1)/ log log n
près, à moins que P = NP [DIN 98]. Un premier algorithme polynomial avec un fac-
teur d’approximation sous-linéaire, O(n/ log n), a été établi pour le problème général
M IN Ek-L IN 2 D ELETION [BER 02].

1.5. Instances particulières de problèmes de satisfaction de contraintes

Certains problèmes d’optimisation deviennent plus faciles à approximer lorsqu’on

se restreint à des instances particulières. Dans cette partie nous allons étudier divers
types d’instances particulières de problèmes d’optimisation : les instances planaires,
denses, avec un nombre borné d’occurrences de chaque variable.

1.5.1. Instances planaires

On parle en général d’instances planaires d’un problème quand le problème est

défini sur un graphe. Dans le cas des problèmes de satisfaisabilité, il existe une manière
naturelle d’associer un graphe à un tel problème.

D ÉFINITION 1.4.– Etant donnée une instance I d’un problème de satisfaction de

contraintes booléennes, m contraintes C1 , . . . , Cm définies sur n variables boo-
léennes x1 , . . . , xn , le graphe associé GI = (V, E) est un graphe biparti défini ainsi :
– V = {x1 , . . . , xn } ∪ {C1 , . . . , Cm } où xi est le sommet associé à la variable xi
et Cj est le sommet associé à la contrainte Cj .
– E = {(xi , Cj ) : xi apparaît dans Cj }.
20 Optimisation Combinatoire

D ÉFINITION 1.5.– Une instance d’un problème de satisfaisabilité est planaire si le

graphe associé est planaire. P LANAR A est le problème A réduit aux instances pla-
naires, où A est un problème de décision ou d’optimisation.

La complexité des instances planaires a été étudiée depuis longtemps. Par exemple
Lichtenstein a montré dans [LIC 82] que P LANAR 3S AT reste NP-difficile et Dyer
et Frieze [DYE 86] ont montré que P LANAR 1 IN 3S AT reste NP-difficile. Plus géné-
ralement, on peut montrer [CRE 01] que pour chaque F -ensemble de contraintes, si
SAT(F ) est NP-complet, alors P LANAR SAT(F ∪ {F, T }) est aussi NP-complet. De
plus, si l’ensemble F n’est pas fermé par complément, alors P LANAR SAT(F ) est
NP-complet quand SAT(F ) est NP-complet. Un exemple de problème SAT(F ) où F
est fermé par complément est NAE3S AT. Kratochvil et Tuza [KRA 00] ont montré
que P LANAR NAE3S AT est polynomial tandis que NAE3S AT est NP-difficile.

En ce qui concerne la complexité d’approximation, Hunt et al. [HUN 94] ont

donné un schéma d’approximation en temps polynomial pour P LANAR M AX kSAT(F )
pour tout ensemble F ce qui implique, par exemple, que P LANAR M AX 3S AT a un
schéma d’approximation. Khanna et Motwani [KHA 96] ont généralisé le résultat
précédent en montrant que P LANAR M AX S AT et plus généralement P LANAR M AX
SAT(F ) ont un schéma d’approximation.

Avant d’expliquer l’idée de ce dernier schéma, définissons la notion de graphe

t-extérieur planaire.

D ÉFINITION 1.6.– Un graphe 1-extérieur planaire est un graphe planaire qui admet
une représentation dans le plan où tous les sommets apparaissent sur la face exté-
rieure. Un graphe t-extérieur planaire est un graphe planaire qui a une représenta-
tion dans le plan telle qu’en effaçant les sommets sur la face extérieure on obtient un
graphe (t − 1)-extérieur planaire.

T HÉORÈME 1.10.– [KHA 96] P LANAR M AX SAT(F ) a un schéma d’approximation.

Preuve : Soit I une instance de P LANAR M AX SAT(F ) avec n variables et m contraintes

et soit GI = (V, E) le graphe associé à I. Puisque |V | = n + m, le graphe GI est
t-extérieur planaire où t ≤ n + m. Soit L1 , . . . , Lt les ensembles de sommets tels
que Lt correspond à la face extérieure et chaque Li est la face extérieure obtenue en
enlevant les sommets des ensembles Lt , . . . , Li+1 .

Considérons une assignation optimale pour I et soit ni le nombre de contraintes sa-

tisfaites correspondant aux sommets appartenant à Li . On partitione les faces L1 , . . . , Lt
en p + 1 groupes S0 , . . . , Sp (où p va être déterminé en fonction de l’erreur maxi-
male ε avec laquelle on veut trouver une solution) où chaque groupe Sr est l’union
des faces Li où i est égal à 3r, 3r + 1 ou 3r + 2 modulo q et q = 3(p + 1).
En utilisant le principe des tiroirs on peut déduire qu’il existe un groupe Sj tel que
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 21

ni ≤ opt(I)
P
Li ∈Sj p+1 . Ce groupe va être déterminé en essayant toutes les possibilités
et en choisissant la meilleure solution. Quand on choisit Sj , on efface les sommets des
faces avec un indice égal à 3j + 1 modulo q, séparant ainsi le graphe en une famille de
graphes disjoints (q −1)-extérieur planaires, G1 , G2 , . . . , Gℓ telle que la somme totale
1
des ni correspondant est au moins (1 − p+1 )opt(I). Un graphe k-extérieur planaire
a une largeur d’arbre d’au plus 3k − 1 ([BOD 98]). En utilisant la programmation
dynamique on peut établir un algorithme polynomial qui fournit une solution opti-
male pour les graphes avec une largeur d’arbre bornée, en particulier pour les graphes
G1 , G2 , . . . , Gℓ . Comme la somme des valeurs des solutions optimales obtenues pour
chaque Gt va être au moins égale à la somme totale des ni correspondant, lorsqu’on
choisit p = ⌈ ε1 − 1⌉ on obtient une approximation à un facteur (1 − ε) près. 

1.5.2. Instances denses

Il existe deux types d’instances denses étudiées dans la littérature : les instances
uniformément denses et les instances denses en moyenne.

D ÉFINITION 1.7.– Une instance d’un problème de M AX kSAT(F ) ou M IN kSAT

D ELETION (F ) sur n variables est uniformément α-dense si pour chaque variable, le
nombre total d’occurrences de la variable et de sa négation est au moins αnk−1 et il
est α-dense en moyenne si le nombre de contraintes est d’au moins αnk .

D ÉFINITION 1.8.– Un ensemble d’instances est uniformément dense s’il existe une
constante α > 0 telle que chaque instance est uniformément α-dense et un ensemble
d’instances est dense en moyenne s’il existe une constante α > 0 telle que chaque
instance est α-dense en moyenne.

Donc, un ensemble d’instances uniformément dense est dense en moyenne mais le

contraire n’est pas vrai.

Arora, Karger et Karpinski [ARO 95] ont débuté l’étude systématique de la com-
plexité d’approximation d’instances denses de problèmes d’optimisation. Ils ont mon-
tré que les instances denses en moyenne (et uniformément denses) de M AX kS AT,
M AX C UT, M AX D I C UT, D ENSE kS UBGRAPH et plus généralement de tout pro-
blème de M AX kSAT(F ) ont un schéma d’approximation en temps polynomial. Arora,
Karger et Karpinski ont remarqué que les optimum des instances denses en moyenne
des problèmes de M AX kSAT(F ) sont "grands" (Ω(nk ) où n est le nombre des va-
riables) et, que dans ce cas, une approximation additive implique une approximation
relative. L’idée de base est de représenter les problèmes comme des programmes ma-
thématiques en nombres entiers d’un certain type [ARO 95], puis d’appliquer des ré-
sultats généraux d’approximation pour ces programmes pour obtenir une approxima-
tion additive.
22 Optimisation Combinatoire

Les instances denses de problèmes de minimisation ont été également étudiées.

Dans [ARO 95], Arora, Karger et Karpinski ont établi des schémas d’approximation
en temps polynomial pour les instances uniformément denses de problèmes de mini-
misation suivants : M IN B ISECTION, M IN kC UT. Pour ces derniers problèmes ils ont
utilisé des idées supplémentaires par rapport aux problèmes de maximisation car les
valeurs des solutions optimales des instances denses des problèmes de minimisation
peuvent être proches de zéro et dans ce cas une approximation additive ne fournit pas
forcément une approximation relative.

Bazgan, Fernandez de la Vega [BAZ 99] ont initié l’étude systématique des ins-
tances denses des versions minimisation des problèmes de satisfaisabilité par le pro-
blème M IN E2-L IN 2 D ELETION. Plus exactement, ils ont montré [BAZ 99] que les
instances uniformément denses de M IN E2-L IN 2 D ELETION ont un schéma d’ap-
proximation en temps polynomial. Dans [BAZ 02, BAZ 03] Bazgan, Fernandez de la
Vega et Karpinski ont généralisé le résultat obtenu pour M IN E2-L IN 2 D ELETION
aux deux problèmes M IN kC ONJ D ELETION, k ≥ 2 et M IN Ek-L IN 2 D ELETION,
k ≥ 3 qui appartiennent à M IN kSAT D ELETION (F ).

Le schéma d’approximation en temps polynomial pour les instances uniformé-

ment denses de ces problèmes de M IN kSAT D ELETION (F ) est constitué de deux
algorithmes (comme dans [ARO 95] pour M IN B ISECTION). Le premier garantit une
bonne solution quand l’optimum du problème est Ω(nk ), le second garantit une bonne
solution quand l’optimum du problème est O(nk ). Quand l’optimum est grand, l’idée
consiste à écrire le problème comme un programme entier d’un certain type puis à
utiliser la méthode de [ARO 95] qui fournit une solution avec une erreur additive de
l’ordre O(nk ). Quand l’optimum est petit, l’idée de l’algorithme est de réaliser un
échantillonnage exhaustif dans un graphe ou hypergraphe et de prendre comme solu-
tion la meilleure obtenue en "complétant" chaque possibilité de placer les variables.
L’algorithme obtenu est un algorithme aléatoire qui peut être dérandomisé comme
dans [ARO 95].

Certains problèmes d’optimisation portant sur des variables booléennes n’admettent

pas de schéma d’approximation en temps polynomial sur les instances uniformément
denses. Un exemple d’un tel problème est M IN 2S AT D ELETION. En fait, on peut
rendre uniformément denses les instances de M IN 2S AT D ELETION, sans changer la
valeur de l’optimum, en ajoutant des copies disjointes des variables originales, puis en
ajoutant toutes les conjonctions ayant exactement une variable originale et une copie.
Comme M IN 2S AT D ELETION n’a pas de schéma d’approximation en temps poly-
nomial, les instances uniformément denses de M IN 2S AT D ELETION n’ont pas de
schéma d’approximation en temps polynomial.

Soulignons que les instances denses en moyenne de M IN kC ONJ D ELETION et

M IN Ek-L IN 2 D ELETION, k ≥ 2, sont aussi difficiles à approximer que les instances
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 23

générales de ces problèmes [BAZ 03]. L’idée est de construire une réduction du cas
général vers le cas particulier en doublant le nombre de variables et considérant toutes
les clauses ou équations sur exactement k variables.

En conclusion, les problèmes de M AX kSAT(F ) ont un schéma d’approxima-

tion pour les instances uniformément denses ainsi que pour les instances denses en
moyenne, par contre la plupart des problèmes de M IN kSAT D ELETION (F ) qui ont
un schéma d’approximation pour les instances uniformément denses restent aussi dif-
ficiles à approximer pour les instances denses en moyenne qu’en général.

1.5.3. Instances avec un nombre borné d’occurrences

Certains problèmes de décision restent NP-complets même dans le cas où chaque

variable n’apparaît qu’un nombre borné de fois.

Notons par EtO CC -EkS AT la variante de EkS AT où chaque clause contient exac-
tement k littéraux et chaque variable apparaît exactement t fois positivement ou néga-
tivement.

T HÉORÈME 1.11.– 3S AT reste NP-complet même quand chaque variable apparaît au

plus 3 fois dont au moins une fois positivement et au moins une fois négativement.

Preuve : L’idée est de réduire 3S AT à ce cas particulier en remplaçant une variable x

qui apparaît k ≥ 3 fois par k copies x1 , . . . , xk et s’assurer que ces k copies prennent
la même valeur de vérité en ajoutant les clauses (x̄1 ∨ x2 ) ∧ (x̄2 ∨ x3 )∧ . . . ∧(x̄k ∨ x1 ).


Dans le théorème précédent il est important que chaque variable apparaisse au plus
(et pas exactement) 3 fois et chaque clause ait au plus (et pas exactement) 3 littéraux
car sinon le problème devient polynomial.

T HÉORÈME 1.12.– [[PAP 94], Problème 9.5.4 (b)] EkO CC -EkS AT, k ≥ 2, est po-
lynomial.

Preuve : Soit I une instance de E3O CC -E3S AT avec n variables x1 , . . . , xn et n

clauses C1 , . . . , Cn . Nous construisons un graphe biparti G = (V1 , V2 , E), où V1 =
{x1 , . . . , xn }, V2 = {C1 , . . . , Cn } et on crée une arête entre xi et Cj si et seulement
si la clause Cj contient xi ou x̄i . Le graphe biparti k-régulier ainsi construit contient
un couplage parfait M = {(xi1 , Cj1 ), . . . , (xin , Cjn )} (en raison du théorème de
König-Hall [HAL 34]) qui peut être trouvé en utilisant par exemple l’algorithme de
Ford-Fulkerson. L’assignation suivante obtenue à partir de M , satisfait I : considerer
xiℓ = 1 si Cjℓ contient xiℓ et xiℓ = 0 si Cjℓ contient x̄iℓ , pour ℓ = 1, . . . , n. 
24 Optimisation Combinatoire

Tovey [TOV 84] a montré que E4O CC -E3S AT est NP-difficile et M AX E4O CC -
E3S AT est APX-difficile et Berman, Karpinski, Scott [BER 03c] ont montré que
ces résultats restent vrais même pour les variantes de ces problèmes où chaque va-
riable apparaît exactement deux fois positivement et deux fois négativement. Du-
bois [DUB 90] a montré la NP-difficulté de E6O CC -E4S AT et E11O CC -E5S AT.
Dans [KRA 93], Kratochvil, Savicky et Tuza ont défini la fonction f (k) comme étant
le plus grand t telle que toute instance de EtO CC -EkS AT est toujours satisfaisable
et ils ont montré que si t > f (k) alors EtO CC -EkS AT est NP-difficile. De plus,
k
f (k+1) ≤ 2f (k)+1 et f (k) ≥ ⌊ 2ek ⌋. Berman, Karpinski et Scott [BER 03b] ont mon-
tré que si t > f (k) alors M AX EtO CC -EkS AT est APX-difficile et ils ont également
amélioré certaines bornes pour la fonction f . Plus exactement, f (5) < 9 et f (6) ≥ 7.
Dans [KAR 01, BER 03a, BER 03b, BER 03c] on peut trouver certaines bornes infé-
rieures et supérieures d’approximation pour divers problèmes, par exemple pour M AX
3O CC -E2S AT, M AX 3O CC -E2-L IN 2 et M IN 3O CC -E3-L IN 2 D ELETION.

1.6. Problèmes de satisfaisabilité sous contraintes globales

Les contraintes de nature globale apparaissent naturellement dans certains pro-

blèmes d’optimisation. Par exemple, M IN B ISECTION est le problème M IN C UT sous
la contrainte que les deux parties séparées par la coupe doivent être de taille égale. Il
est connu que M IN C UT est polynomial tandis que M IN B ISECTION est NP-difficile.
Plusieurs problèmes d’optimisation comme par exemple M AX B ISECTION et M IN
B ISECTION peuvent se formuler comme des problèmes de satisfaction de contraintes
booléennes où une solution réalisable est une solution avec autant de variables fixées
à 0 que de variables fixées à 1. Par exemple, pour une instance de M IN B ISECTION
représentée par un graphe G avec n sommets et m arêtes on considère n variables
booléennes x1 , . . . , xn et m contraintes en associant à chaque arête (i, j) de G la
contrainte xi ⊕ xj = 0. Ainsi, M IN B ISECTION est le problème consistant à trouver
une solution avec autant de variables à 0 qu’à 1 tel qu’un nombre minimum parmi les
m contraintes précédentes soit non satisfaites.

D ÉFINITION 1.9.– Une assignation est appelée équilibrée si le nombre de variables

fixées à 1 est le même que le nombre de variables fixées à 0. BALANCED A est la
variante du problème A où les solutions réalisables sont des assignations équilibrées
et A est un problème de décision ou d’optimisation.

Les complexités exacte et d’approximation des versions équilibrées des problèmes

de satisfaisabilité de décision et d’optimisation ont été étudiées par Bazgan et Kar-
pinski dans [BAZ 05]. De manière générale, si un problème est difficile, sa version
équilibrée reste difficile. En revanche, plusieurs problèmes triviaux deviennent diffi-
ciles.
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 25

Plus précisément, si SAT(F ) est NP-complet alors BALANCED SAT(F ) est aussi
NP-complet [BAZ 05]. Il est facile de voir que M ONOTONE -EkS AT est trivial car l’as-
signation 1 pour chaque variable (si la formule est composée seulement de littéraux
positifs) ou l’assignation 0 pour chaque variable (si la formule est composée seule-
ment de littéraux négatifs) est une assignation satisfaisante. En revanche, BALANCED
M ONOTONE -EkS AT est NP-complet, pour tout k ≥ 2 ([BAZ 05]). Comme spécifié
dans le Théorème 1.3, Ek-L IN 2, pour tout k ≥ 2 est polynomial. Dans le cas équili-
bré, la situation est différente car pour k = 2 le problème reste polynomial, par contre
pour k ≥ 3 le problème devient NP-complet même pour un ensemble d’équations
linéaires 0-homogène ou 1-homogène [BAZ 05].

Les versions équilibrées des problèmes de maximisation ont été également étu-
diées. Comme dans le cas des problèmes de décision, on peut montrer que M AX
SAT(F ) est E-réductible à BALANCED M AX SAT(F ) ([BAZ 05]). Il s’ensuit que
la version équilibrée est au moins aussi difficile à approximer que la version géné-
rale. De plus, BALANCED M AX M ONOTONE -EkS AT est APX-difficile, pour tout
k ≥ 2 [BAZ 05]. BALANCED M AX S AT est approximable à un facteur (1 − 1e )
près [SVI 01] et BALANCED M AX 2S AT est approximable à un facteur 0,66 près
[BLA 02] et aléatoirement approximable à un facteur 34 près [HOF 03]. BALANCED
M AX M ONOTONE -EkC ONJ, k ≥ 2, n’a pas de schéma d’approximation si NP 6⊆
δ
∩δ>0 BTIME(2n ) [BAZ 05]. BALANCED M AX E2-L IN 2 dans le cas 1-homogène,
qui correspond à M AX B ISECTION est APX-difficile [PAP 88, HÅS 97] et BALAN -
CED M AX E2-L IN 2 dans le cas 0-homogène, qui correspond à BALANCED M AX
δ
U N C UT n’a pas de schéma d’approximation si NP 6⊆ ∩δ>0 BTIME(2n ) [BAZ 05].
De plus, BALANCED M AX Ek-L IN 2 est APX-difficile, pour tout k ≥ 3 même dans
le cas 0-homogène ou 1-homogène [BAZ 05]. Également, utilisant la technique PCP
(Probabilistically Checkable Proof), Holmerin [HOL 02] a montré, que le problème
BALANCED M AX E4-L IN 2 dans le cas 0-homogène n’est pas approximable à un
facteur 0,912 près et Holmerin et Khot [HOL 03] ont montré que le problème BA -
LANCED M AX E3-L IN 2 dans le cas 0-homogène n’est pas approximable à un facteur
( 43 − ε) près, pour tout ε > 0. Récemment, Holmerin et Khot [HOL 04] ont montré
que le problème BALANCED M AX E3-L IN 2 dans le cas 0-homogène n’est pas ap-
δ
proximable à un facteur ( 21 − ε) près, pour tout ε > 0, si NP 6⊆ ∩δ>0 DTIME(2n ),
obtenant ainsi le meilleur résultat de non-approximabilité pour ce problème car il est
facilement approximable à un facteur 12 près.

Pour les problèmes de minimisation, on peut établir le même résultat que pour
les problèmes de maximisation : BALANCED M IN SAT D ELETION (F ) est au moins
aussi difficile à approximer que M IN SAT D ELETION (F ), pour tout ensemble F . BA -
LANCED M IN M ONOTONE -EkS AT D ELETION , k ≥ 2, n’a pas de schéma d’approxi-
mation si P6=NP and BALANCED M IN M ONOTONE -EkC ONJ D ELETION, k ≥ 2,
δ
n’a pas de schéma d’approximation si NP 6⊆ ∩δ>0 BTIME(2n ) [BAZ 05]. Holme-
rin et Khot [HOL 03] ont établi une borne inférieure pour une généralisation de M IN
26 Optimisation Combinatoire

B ISECTION. Plus précisément, ils ont montré que BALANCED M IN E3-L IN 2 D ELE -
TION , même dans les cas 0-homogène et 1-homogène, n’est pas c-approximable, pour
toute constante c > 1, si P 6= NP. BALANCED M IN E2-L IN 2 D ELETION dans le cas
1-homogène correspond à BALANCED M IN U N C UT qui a été montré APX-difficile
[GAR 93]. BALANCED M IN E2-L IN 2 D ELETION dans le cas 0-homogène est M IN
B ISECTION. La complexité d’approximation de M IN B ISECTION n’est pas établie.
Le meilleur algorithme approche le problème à un facteur O(log n2 ) près [FEI 00].
δ
Récemment, Khot [KHO 04] a établi que si NP 6⊆ ∩δ>0 BTIME(2n ) alors M IN B I -
SECTION n’a pas de schéma d’approximation en temps polynomial. BALANCED M IN
Ek-L IN 2 D ELETION, pour k ≥ 4, dans les cas 0-homogène et 1-homogène n’a pas
de schéma d’approximation si P 6= NP [BAZ 05].

1.7. Conclusion

Les problèmes de satisfaisabilité restent des problèmes centraux en théorie de la

complexité. Ce chapitre montre le progrès théorique considérable réalisé sur l’étude
des problèmes de satisfaisabilité pendant les dernières décennies. Nous disposons ac-
tuellement d’une caractérisation presque complète de la complexité exacte et d’ap-
proximation de ces problèmes ainsi que de diverses instances particulières.

1.8. Bibliographie

[ARO 95] A RORA S., K ARGER D., K ARPINSKI M., « Polynomial time approximation
schemes for dense instances of NP-hard problems », Proceedings of 27th Annual ACM
Symposium on the Theory of Computing, p. 284–293, 1995, Also published in Journal of
Computer and System Sciences 58, 1999, 193–210.
[ASA 00] A SANO T., W ILLIAMSON D. P., « Improved approximation algorithms for MAX
SAT », Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms, p. 96-105,
2000.
[AVI 02] AVIDOR A., Z WICK U., « Approximating MIN 2-SAT and MIN 3-SAT », Procee-
ding of 13th Annual International Symposium on Algorithms and Computation, 465-475,
vol. LNCS 2518, Springer-Verlag, 2002, Also published in Theory of Computing Systems
38(3), 2005, 329–345.
[BAZ 99] BAZGAN C., F ERNANDEZ DE LA V EGA W., « A polynomial time approximation
scheme for dense M IN 2S AT », C IOBANU G., PAUN G., Eds., Proceedings of the 12th Inter-
national Symposium on the Fundamentals of Computation Theory, LNCS 1684, Springer-
Verlag, p. 91–99, 1999.
[BAZ 02] BAZGAN C., F ERNANDEZ DE LA V EGA W., K ARPINSKI M., « Approximability of
Dense Instances of Nearest Codeword Problem », P ENTTONEN M., M EINECHE S CHMIDT
E., Eds., Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, LNCS 2368,
Springer-Verlag, p. 298–307, 2002.
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 27

[BAZ 03] BAZGAN C., F ERNANDEZ DE LA V EGA W., K ARPINSKI M., « Polynomial time
approximation schemes for dense instances of the minimum constraint satisfaction », Ran-
dom Structures and Algorithms, vol. 23(1), p. 73–91, 2003.
[BAZ 05] BAZGAN C., K ARPINSKI M., « On the Complexity of Global Constraint Satisfac-
tion », Proceeding of 16th Annual International Symposium on Algorithms and Computa-
tion, vol. LNCS 3827, Springer-Verlag, p. 624–633, 2005.
[BER 96] B ERTSIMAS D., T EO C.-P., VOHRA R., « On dependent randomized rounding al-
gorithms », Proceeding of the 5th International Integer Programming and Combinatorial
Optimization Conference, vol. LNCS 1084, Springer-Verlag, p. 330–344, 1996.
[BER 02] B ERMAN P., K ARPINSKI M., « Approximation Hardness of Bounded Degree MIN-
CSP and MIN-BISECTION », Proceeding of the 29th International Colloquium on Auto-
mata, Languages and Programming, vol. LNCS 2380, Springer-Verlag, p. 623-632, 2002.
[BER 03a] B ERMAN P., K ARPINSKI M., Improved Approximation Lower Bounds on Small
Occurrence Optimization, ECCC Technical Report, TR03-008, 2003.
[BER 03b] B ERMAN P., K ARPINSKI M., S COTT A., Approximation Hardness and Satisfiabi-
lity of Bounded Occurrence Instances of SAT, ECCC Technical Report, TR03-022, 2003.
[BER 03c] B ERMAN P., K ARPINSKI M., S COTT A., Approximation Hardness of Short Sym-
metric Instances of MAX-3SAT, ECCC Technical Report, TR03-049, 2003.
[BLA 02] B LASER M., M ANTHEY B., « Improved Approximation Algorithms for Max 2Sat
with Cardinality Constraint », Proceedings of the 13th Annual International Symposium on
Algorithms and Computation, LNCS 2518, Springer-Verlag, p. 187–198, 2002.
[BOD 98] B ODLAENDER H. L., « A partial k-arboretum of graphs with bounded treewidth »,
Theoretical Computer Science, vol. 209, p. 1–45, 1998.
[COO 71] C OOK S., « The complexity of theorem-proving procedures », Proceedings of the
3rd Annual ACM Symposium on Theory of Computing, p. 151–158, 1971.
[CRA 94] C RAWFORD J., BAKER A., « Experimental results on the application of satisfiability
algorithms to scheduling problems », Proceedings of the 12th National Conference on IA,
p. 1092–1097, 1994.
[CRE 95a] C REIGNOU N., « A dichotomy theorem for maximum generalized satisfiability
problems », Journal of Computer and Systeme Sciences, vol. 51(3), p. 511–522, 1995.
[CRE 95b] C RESCENZI P., K ANN V., A compendium of NP optimization problems,
http ://www.nada.kth.se/∼viggo/problemlist/compendium.html, 1995.
[CRE 96] C RESCENZI P., S ILVESTRI R., T REVISAN L., « To weight or not to weight : where
is the question ? », Proceedings of the 4th Israeli Symposium on Theory of Computing and
Systems, p. 68–77, 1996.
[CRE 01] C REIGNOU N., K HANNA K., S UDAN M., Complexity Classifications of Boolean
Constraint Satisfaction Problems, SIAM Monographs on Discrete Mathematics and Appli-
cations, 2001.
28 Optimisation Combinatoire

[DIN 98] D INUR I., K INDLER G., S AFRA S., « Approximating-CVP to within almost-
polynomial factors is NP-hard », Proceeding of the 39th IEEE Annual Symposium on Foun-
dations of Computer Science, p. 99–109, 1998.
[DOW 84] D OWLING W. F., G ALLIER J. H., « Linear time algorithms for testing the satisfia-
bility of propositional Horn formulae », Journal of Logic Programming, vol. 3, p. 267–284,
1984.
[DUB 90] D UBOIS O., « On the r,s-SAT satisfiability problem and a conjecture of Tovey »,
Discrete Applied Mathematics, vol. 26, p. 51–60, 1990.
[DYE 86] DYER M., F RIEZE A., « Planar 3DM is NP-complete », Journal of Algorithms,
vol. 7, p. 174–184, 1986.
[ERD 73] E RD ŐS P., S ELFRIDGE J., « On a combinatorial game », Journal of Combinatorial
Theory A, vol. 14, p. 298–301, 1973.
[FEI 95] F EIGE U., G OEMANS M. X., « Approximating the value of two prover proof sys-
tems, with applications to MAX 2SAT and MAX DICUT », Proceedings of the 3rd Istrael
Symposium on Theory of Computing and Systems, p. 182–189, 1995.
[FEI 00] F EIGE U., K RAUTHGAMER R., « A polylogarithmic approximation of the Mini-
mum Bisection », Proceedings of the 41st Annual Symposium on Foundations of Computer
Science, p. 105–115, 2000.
[GAR 74] G AREY M. R., J OHNSON D. S., S TOCKMEYER L., « Some simplified NP-
complete problems », Proceedings of the Conference record of 6th Annual ACM Symposium
on Theory of Computing, p. 47–63, 1974, Also published in Theoretical Computer Science,
1, 1976, 237–267.
[GAR 79] G AREY M. R., J OHNSON D. S., Computers and Intractability / A Guide to the
Theory of NP-Completeness, W.H. Freeman & Company, San Francisco, 1979.
[GAR 93] G ARG N., VAZIRANI V., YANNAKAKIS M., « Approximate Max-flow Min-
(multi)cut Theorems and Their Applications », Proceedings of the 25th Annual ACM Sym-
posium on the Theory of Computing, p. 698–707, 1993, Also published in SIAM Journal
on Computing, 25, 1996, 235–251.
[GEN 99] G ENT I., WALSH T., The search for Satisfaction, Rapport, 1999, Internal Report,
Dept. of Computer Science, University of Strathclyde.
[GOE 94] G OEMANS M., W ILLIAMSON D., « New 3/4-approximation algorithms for Max
Sat », SIAM Journal on Discrete Mathematics, vol. 7, p. 656–666, 1994.
[GOE 95] G OEMANS M., W ILLIAMSON D., « Improved Approximation Algorithms for
Maximum Cut and Satisfiability Problems Using Semidefinite Programming », Journal
of the ACM, vol. 42, p. 1115–1145, 1995.
[GU 97] G U J., P URDOM P., F RANCO J., WAH B., « Algorithms for the Satisfiability pro-
blem : a survey », DIMACS Series on Discrete Mathematics and Theoretical Computer
Science, American Mathematical Society 35, p. 19–151, 1997.
[HAL 34] H ALL P., « On representations of subsets », Journal London Math. Soc., vol. 10,
page 26, 1934.
 Complexité des Problèmes de Satisfaction de Contraintes Booléennes 29

[HÅS 97] H ÅSTAD J., « Some optimal inapproximability results », Proceedings of the 29th
Annual ACM Symposium on the Theory of Computing, p. 1–10, 1997.
[HOF 03] H OFMEISTER T., « An Approximation Algorithm for MAX-2-SAT with Cardinality
Constraint », Proceedings of the 11th Annual European Symposium on Algorithms, LNCS
2832, Springer-Verlag, p. 301–312, 2003.
[HOL 02] H OLMERIN J., PCP with Global Constraints - Balanced Homogeneous Linear Equa-
tions, manuscript, 2002.
[HOL 03] H OLMERIN J., K HOT S., « A strong inapproximability result for a generalization
of Minimum Bisection », Proceedings of the 18th IEEE Conference on Computational
Complexity, p. 371–378, 2003.
[HOL 04] H OLMERIN J., K HOT S., « A new PCP Outer Verifier with Applications to Ho-
mogeneous Linear Equations and Max-Bisection », Proceedings of the 36th Annual ACM
Symposium on Theory of Computing, p. 11–17, 2004.
[HOO 98] H OOS H., Stochastic Local Search - Methods, Models, Applications,
http ://www.cs.ubc.ca/spider/hoos/publ-ai.html, 1998, PhD thesis, TU Darmstadt.
[HUN 94] H UNT III H., M ARATHE M., R ADHAKRISHNAN V., R AVI S., ROSENKRANTZ D.,
S TEARNS R., « Approximation Schemes using L-reductions », Proceedings of the 14th
Conference on Foundations of Software Technology and Theoretical Computer Science,
LNCS 880, Springer-Verlag, p. 342–353, 1994.
[JIA 95] J IANG Y., K AUTZ H., S ELMAN B., « Solving problems with hard and soft constraints
using a stochastic algorithm for Max-Sat », First International Joint Workshop on Artificial
Intelligence and Operation Research, p. 1–15, 1995.
[JOH 74] J OHNSON D. S., « Approximation algorithms for combinatorial problems », Journal
of Computer and System Sciences, vol. 9, p. 256–278, 1974.
[JON 77] J ONES N. D., L AASER W. T., « Complete problems for deterministic polynomial
time », Theoretical Computer Sciences, vol. 3, p. 107–117, 1977.
[KAR 01] K ARPINSKI M., « Approximating bounded degree instances of NP-hard problems »,
Proceedings of the 13th Symposium on Fundamentals of Computation Theory, LNCS 2138,
Springer-Verlag, p. 24–34, 2001.
[KAU 92] K AUTZ H., S ELMAN B., « Planning as Satisfiability », Proceedings of the 10th
ECAI, p. 359–363, 1992.
[KHA 96] K HANNA S., M OTWANI R., « Towards a syntactic characterization of PTAS », Pro-
ceedings of the 28th Annual ACM Symposium on Theory of Computing, p. 329–337, 1996.
[KHA 97a] K HANNA S., S UDAN M., T REVISAN L., « Constraint Satisfaction : The Approxi-
mability of Minimization Problems », Proceedings of the 12th Annual IEEE Conference on
Computational Complexity, p. 282–296, 1997.
[KHA 97b] K HANNA S., S UDAN M., W ILLIAMSON D., « A Complete Classification of the
Approximability of Maximization Problems Derived from Boolean Constraint Satisfac-
tion », Proceedings of the 29th Annual ACM Symposium on Theory of Computing, p. 11–20,
1997.
30 Optimisation Combinatoire

[KHO 04] K HOT S., « Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bi-
partite Clique », Proceedings of the 45th Annual IEEE Symposium on Foundations of Com-
puter Science, p. 136–145, 2004.
[KLA 96] K LAUCK H., « On the hardness of global and local approximation », Proceedings of
the 5th Scandinavian Workshop on Algorithm Theory, LNCS 1097, Springer-Verlag, p. 88–
99, 1996.
[KLE 97] K LEIN P., P LOTKIN S., R AO S., TARDOS E., « Approximation Algorithms for Stei-
ner and Directed Multicuts », Journal of Algorithms, vol. 22, n˚2, p. 241-269, 1997.
[KOH 94] KOHLI R., K RISHNAMURTI R., M IRCHANDANI P., « The Minimum Satisfiability
Problem », SIAM Journal on Discrete Mathematics, vol. 7, p. 275–283, 1994.
[KRA 93] K RATOCHVIL J., S AVICKY P., T UZA Z., « One more occurence of variable makes
satisfiability jump from trivial to NP-complete », SIAM Journal on Computing, vol. 22(1),
p. 203–210, 1993.
[KRA 00] K RATOCHVIL J., T UZA Z., « On the complexity of bicoloring clique hypergraphs
of graphs (extended abstract) », Proceedings of the 11th Annual ACM-SIAM Symposium on
Discrete Algorithms, p. 40–41, 2000.
[LEV 73] L EVIN L. A., « Universal sorting problems », Problems of Information Transmis-
sion, vol. 9, p. 265–266, 1973.
[LIC 82] L ICHTENSTEIN D., « Planar formulae and their uses », SIAM Journal on Computing,
vol. 11(2), p. 329–343, 1982.
[MIN 88] M INOUX M., « LTUR : A simplified linear-time unit resolution algorithm for Horn
formulae and computer implementation », Information Processing Letters, vol. 29, p. 1–12,
1988.
[PAP 88] PAPADIMITRIOU C., YANNAKAKIS M., « Optimization, Approximation, and Com-
plexity Classes », Proceedings of the 20th Annual ACM Symposium on Theory of Compu-
ting, p. 229–234, 1988, Also published in Journal of Computer and System Sciences, 43,
1991, 425–440.
[PAP 94] PAPADIMITRIOU C., Computational Complexity, Addison-Wesley Publishing Com-
pany, 1994.
[SCH 78] S CHAEFER T., « The complexity of satisfiability problems », In Conference Record
of the 10th Annual ACM Symposium on Theory and Computing, p. 216–226, 1978.
[SVI 01] S VIRIDENKO M. I., « Best possible approximation algorithm for MAX SAT with
cardinality constraint », Algorithmica, vol. 30(3), p. 398–405, 2001.
[TAR 72] TARJAN R., « Depth first search and linear graph algorithms », SIAM Journal on
Comput., vol. 1(2), p. 146–160, 1972.
[TOV 84] T OVEY C., « A simplified satisfiability problem », Discrete Applied Mathematics,
vol. 8, p. 85–89, 1984.
[TRE 96] T REVISAN L., « Parallel Approximation Algorithms by Positive Linear Program-
ming », Proceedings of the 4th European Symposium on Algorithms, LNCS 1136, Springer-
Verlag, p. 62–75, 1996, Also published in Algorithmica, 21, 72–88, 1998.
 Chapitre 2

Index

(anti-)Horn, 7, 10, 12 affine, 7

L IN 2, 5, 11, 25 assignation, 4
M AX C ONJ, 8, 18, 25 équilibrée, 24
M AX L IN 2, 9, 18, 24, 25 bijonctive, 7, 12
M AX S AT , 8, 12, 14, 15, 17, 18, 20, 21, 25
contraintes globales, 24
M IN C ONJ D ELETION, 8, 19, 22, 25
instances
M IN L IN 2 D ELETION, 9, 19, 22, 26
M IN S AT D ELETION, 8, 19, 22, 25 0 ou 1-homogènes, 8, 25, 26
S AT , 5, 9, 20, 23, 25 denses, 21
0 ou 1-valide, 7, 12, 14 nombre borné d’occurrences, 23
2-monotone, 7, 12, 14 planaires, 19

31