Upload
adrien-guillaume
View
106
Download
0
Embed Size (px)
Citation preview
16 mars 2007 Cours de graphes 7 - Intranet 1
Cours de graphesCours de graphes
Problèmes NP-complets.Problèmes NP-complets.
Réductions polynômiales.Réductions polynômiales.
16 mars 2007 Cours de graphes 7 - Intranet 2
Les grandes lignes du coursLes grandes lignes du cours
•Définitions de baseDéfinitions de base•ConnexitéConnexité•Les plus courts cheminsLes plus courts chemins•Dijkstra et Bellmann-FordDijkstra et Bellmann-Ford•ArbresArbres•Arbres de recouvrement minimaux Arbres de recouvrement minimaux •Problèmes de flotsProblèmes de flots•Coloriage de graphes, graphes Coloriage de graphes, graphes planairesplanaires•CouplageCouplage•Chemins d’Euler et de HamiltonChemins d’Euler et de Hamilton•Problèmes NP-completsProblèmes NP-complets
16 mars 2007 Cours de graphes 7 - Intranet 3
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
R A P P E L SR A P P E L S
S U R L AS U R L A
N P – C O M P L E T U D EN P – C O M P L E T U D E
16 mars 2007 Cours de graphes 7 - Intranet 4
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• La question :La question :
• Y aurait-il par hasard des problèmes dont la Y aurait-il par hasard des problèmes dont la complexité intrinsèque est exponentielle ?complexité intrinsèque est exponentielle ?
• Pour un tel problème, tout algorithme pour le Pour un tel problème, tout algorithme pour le résoudre serait exponentiel en temps !résoudre serait exponentiel en temps !
16 mars 2007 Cours de graphes 7 - Intranet 5
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• La question :La question :
• Y aurait-il par hasard des problèmes dont la complexité Y aurait-il par hasard des problèmes dont la complexité intrinsèque est exponentielle ?intrinsèque est exponentielle ?
• Pour un tel problème, tout algorithme pour le résoudre serait Pour un tel problème, tout algorithme pour le résoudre serait exponentiel en temps !exponentiel en temps !
• La réponse :La réponse :
• Probablement OUI !Probablement OUI !
• Malheureusement ! ! !Malheureusement ! ! !
• On ne sait rien de définitif ! ! !On ne sait rien de définitif ! ! !
P = N PP = N P
ou bienou bien
P = N PP = N P
//
16 mars 2007 Cours de graphes 7 - Intranet 6
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• La classe de problèmes « La classe de problèmes « P »P » ! !
• Ce sont les problèmes qui acceptent un algorithme : Ce sont les problèmes qui acceptent un algorithme :
– polynômial,polynômial,
– déterministe,déterministe,
– qui résout toutes les instances.qui résout toutes les instances.
16 mars 2007 Cours de graphes 7 - Intranet 7
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• La classe de problèmes « La classe de problèmes « P »P » ! !
• Ce sont les problèmes qui acceptent un algorithme : Ce sont les problèmes qui acceptent un algorithme :
– polynômial,polynômial,
– déterministe,déterministe,
– qui résout toutes les instances.qui résout toutes les instances.
La complexité est un polynômeLa complexité est un polynômeen termes de la taille du problème.en termes de la taille du problème.
Il n’y a aucun élément de chance ouIl n’y a aucun élément de chance oud’indication venant de l’extérieur.d’indication venant de l’extérieur.
Aucune instanceAucune instancen’est trop difficile.n’est trop difficile.
16 mars 2007 Cours de graphes 7 - Intranet 8
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• La classe de problèmes « La classe de problèmes « N N P »P » ! !
• Ce sont les problèmes qui acceptent un algorithme : Ce sont les problèmes qui acceptent un algorithme :
– polynômial,polynômial,
– nonnon--déterministe,déterministe,
– qui résout toutes les instances.qui résout toutes les instances.
16 mars 2007 Cours de graphes 7 - Intranet 9
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• La classe de problèmes « La classe de problèmes « N N P »P » ! !
• Ce sont les problèmes qui acceptent un algorithme : Ce sont les problèmes qui acceptent un algorithme :
– polynômial,polynômial,
– nonnon--déterministe,déterministe,
– qui résout toutes les instances.qui résout toutes les instances.
Il peut y a avoir des élémentsIl peut y a avoir des élémentsde chance ou desde chance ou des
indications venant de l’extérieur.indications venant de l’extérieur.
16 mars 2007 Cours de graphes 7 - Intranet 10
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Nous remplaçons une exploration à l’aide du back-track Nous remplaçons une exploration à l’aide du back-track
– par un appel à l’oracle.par un appel à l’oracle.
• L’oracle répond au bout de . . . ?L’oracle répond au bout de . . . ?
– La complexité de l’oracle est bien-sûr en O ( 1 ) .La complexité de l’oracle est bien-sûr en O ( 1 ) .
• Je sais réaliser un oracle en temps exponentiel !Je sais réaliser un oracle en temps exponentiel !
– Il suffit de faire un back-track en cachette ! ! !Il suffit de faire un back-track en cachette ! ! !
16 mars 2007 Cours de graphes 7 - Intranet 11
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Autre formulation de la classe de Autre formulation de la classe de problèmes « problèmes « N N P »P » ! !
• Ce sont les problèmes qui : Ce sont les problèmes qui :
– acceptent, pour chaque instance, un nombre acceptent, pour chaque instance, un nombre borné de candidats à être la solution,borné de candidats à être la solution,
– pour lesquels, la vérification qu’un candidat pour lesquels, la vérification qu’un candidat quelconque est solution appartient à « quelconque est solution appartient à « P P ». ».
16 mars 2007 Cours de graphes 7 - Intranet 12
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Théorème :Théorème :
P N PP N P
UU
N PN P
PP
16 mars 2007 Cours de graphes 7 - Intranet 13
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Théorème :Théorème :
P N PP N P
UU
N PN P
PP
P = N P P = N P c’est-à-dire c’est-à-dire N P \ P = N P \ P = oo//?? ??
? ? ? ? ?? ? ? ? ?
16 mars 2007 Cours de graphes 7 - Intranet 14
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Définissons la classe « Définissons la classe « N P C N P C », c’est-à-dire les », c’est-à-dire les problèmes « Nproblèmes « N--PP--complets » :complets » :
N PN P
PP
N P CN P C
16 mars 2007 Cours de graphes 7 - Intranet 15
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Définissons la classe « Définissons la classe « N P C N P C », c’est-à-dire les », c’est-à-dire les problèmes « Nproblèmes « N--PP--complets » :complets » :
N PN P
PP
N P CN P C
Ce seront les problèmes les plus difficiles de « Ce seront les problèmes les plus difficiles de « N P » !N P » !
L’idée : Si eux sont dans « L’idée : Si eux sont dans « PP », alors », alors « « P = N P P = N P »» ! ! !! ! !
Facile.Facile.
Difficile.Difficile.
16 mars 2007 Cours de graphes 7 - Intranet 16
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Il nous faut une notion de traduction !Il nous faut une notion de traduction !
– Soit un problème P : D Soit un problème P : D --> BOOL> BOOL
– Soit un problème P : D Soit un problème P : D --> BOOL> BOOL
1111
2222
16 mars 2007 Cours de graphes 7 - Intranet 17
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Il nous faut une notion de traduction !Il nous faut une notion de traduction !
– Soit un problème P : D Soit un problème P : D --> BOOL> BOOL
– Soit un problème P : D Soit un problème P : D --> BOOL> BOOL
• P se réduit polynômialement en P , noté P <= P P se réduit polynômialement en P , noté P <= P
si et seulement si :si et seulement si :
– il existe f : D il existe f : D --> D avec f > D avec f PP
– telle que pour tout x telle que pour tout x D : D :
P ( x ) = P ( f ( x ) )P ( x ) = P ( f ( x ) )
1111
2222
11 1122 22
11 22
11
11 22
PP
16 mars 2007 Cours de graphes 7 - Intranet 18
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• L’idée derrière la traduction :L’idée derrière la traduction :
PP11
xx Vrai ou FauxVrai ou FauxCalcul !Calcul !
PP22
f ( x )f ( x )
Traduction !Traduction !
Vrai ou FauxVrai ou FauxCalcul !Calcul !
Le mêmeLe mêmerésultat !résultat !
16 mars 2007 Cours de graphes 7 - Intranet 19
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Définition :Définition :
• La classe « La classe « N P CN P C » est la classe des problèmes P tels » est la classe des problèmes P tels que :que :
– P P N PN P . .
– Pour tout Q Pour tout Q N PN P on a : Q <= P . on a : Q <= P .PP
16 mars 2007 Cours de graphes 7 - Intranet 20
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Définition :Définition :
• La classe « La classe « N P CN P C » est la classe des problèmes P tels que : » est la classe des problèmes P tels que :
– P P N PN P . .
– Pour tout Q Pour tout Q N PN P on a : Q <= P . on a : Q <= P .
• Tout le monde se réduit vers P .Tout le monde se réduit vers P .
• P est donc le plus difficile ! ! !P est donc le plus difficile ! ! !
• Si P , P’ Si P , P’ N P CN P C , alors il sont ex aequo en difficulté : , alors il sont ex aequo en difficulté :
P <= P’ et P’ <= P .P <= P’ et P’ <= P .
PP PP
PP
16 mars 2007 Cours de graphes 7 - Intranet 21
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Et si « Et si « N P CN P C » était vide ? ? ? » était vide ? ? ?
– C’est-à-dire, un tel problème universel n’existe pas ! ! C’est-à-dire, un tel problème universel n’existe pas ! ! !!
• Théorème (Cook, 1971) :Théorème (Cook, 1971) :
– SAT SAT N P CN P C . .
16 mars 2007 Cours de graphes 7 - Intranet 22
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Et si « Et si « N P CN P C » était vide ? ? ? » était vide ? ? ?
– C’est-à-dire, un tel problème universel n’existe pas ! ! !C’est-à-dire, un tel problème universel n’existe pas ! ! !
• Théorème (Cook, 1971) :Théorème (Cook, 1971) :
– SAT SAT N P CN P C . .
• Il n’y a pas plus difficile (dans Il n’y a pas plus difficile (dans N P CN P C) que la logique.) que la logique.
• Principe de la preuve :Principe de la preuve :
– Tout problème dans « Tout problème dans « N PN P » peut être traduit en une formule » peut être traduit en une formule logique.logique.
– Analogie : Tout texte peut être traduit en une formule Analogie : Tout texte peut être traduit en une formule alphabétique.alphabétique.
16 mars 2007 Cours de graphes 7 - Intranet 23
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
N PN P
PP
N P CN P CSATSAT
16 mars 2007 Cours de graphes 7 - Intranet 24
• Conséquences :Conséquences :
• S’il existe un seul problème PS’il existe un seul problème P N P CN P C
– pour lequel on trouve un algorithme en temps pour lequel on trouve un algorithme en temps polynômial et déterministe,polynômial et déterministe,
– alors alors P = N P P = N P !!
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
16 mars 2007 Cours de graphes 7 - Intranet 25
• Conséquences :Conséquences :
• S’il existe un seul problème PS’il existe un seul problème P N P CN P C
– pour lequel on trouve un algorithme en temps polynômial pour lequel on trouve un algorithme en temps polynômial et déterministe,et déterministe,
– alors alors P = N P P = N P !!
• S’il existe un seul problème PS’il existe un seul problème P N P CN P C
– pour lequel on prouve qu’un algorithme en temps pour lequel on prouve qu’un algorithme en temps polynômial et déterministe ne peut pas exister,polynômial et déterministe ne peut pas exister,
– alors alors P = N P P = N P !!
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
//
16 mars 2007 Cours de graphes 7 - Intranet 26
• Conséquences :Conséquences :
• S’il existe un seul problème PS’il existe un seul problème P N P CN P C
– pour lequel on trouve un algorithme en temps polynômial pour lequel on trouve un algorithme en temps polynômial et déterministe,et déterministe,
– alors alors P = N P P = N P !!
• S’il existe un seul problème PS’il existe un seul problème P N P CN P C
– pour lequel on prouve qu’un algorithme en temps pour lequel on prouve qu’un algorithme en temps polynômial et déterministe ne peut pas exister,polynômial et déterministe ne peut pas exister,
– alors alors P = N P P = N P !!
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
//
16 mars 2007 Cours de graphes 7 - Intranet 27
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Concrètement :Concrètement :
• Vous avez un problème qui vous résiste ?Vous avez un problème qui vous résiste ?
• Essayez de savoir s’il est Essayez de savoir s’il est NN--PP--complet !complet !
– le Garey and Johnson, ou Internet, ou . . .le Garey and Johnson, ou Internet, ou . . .
16 mars 2007 Cours de graphes 7 - Intranet 28
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Concrètement :Concrètement :
• Vous avez un problème qui vous résiste ?Vous avez un problème qui vous résiste ?
• Essayez de savoir s’il est Essayez de savoir s’il est NN--PP--complet !complet !
– le Garey and Johnson, ou Internet, ou . . .le Garey and Johnson, ou Internet, ou . . .
• Comment prouver qu’il est Comment prouver qu’il est NN--PP--complet ? ? ?complet ? ? ?
– Prouvez que votre problème P est dans Prouvez que votre problème P est dans N P N P etet
– prenez un problème A de prenez un problème A de N P C N P C et montrez queet montrez que
A <= PA <= P
PP
16 mars 2007 Cours de graphes 7 - Intranet 29
Rappels sur la NPRappels sur la NP--complétudecomplétude----------------------------------------------------------------------------------------------------------------------------------
• Concrètement :Concrètement :
• Vous avez un problème qui vous résiste ?Vous avez un problème qui vous résiste ?
• Essayez de savoir s’il est Essayez de savoir s’il est NN--PP--complet !complet !
– le Garey and Johnson, ou Internet, ou . . .le Garey and Johnson, ou Internet, ou . . .
• Comment prouver qu’il est Comment prouver qu’il est NN--PP--complet ? ? ?complet ? ? ?
– Prouvez que votre problème P est dans Prouvez que votre problème P est dans N P N P etet
– prenez un problème A de prenez un problème A de N P C N P C et montrez queet montrez que
A <= PA <= P
PP
On vous donneOn vous donnela solution etla solution etvous vérifiezvous vérifiezque c’en estque c’en est
bien une !bien une !
16 mars 2007 Cours de graphes 7 - Intranet 30
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
Q U E L Q U E SQ U E L Q U E S
R E D U C T I O N SR E D U C T I O N S
P O L Y N O M I A L E SP O L Y N O M I A L E S
16 mars 2007 Cours de graphes 7 - Intranet 31
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et VERTEX C.et VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 32
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et VERTEX C.et VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 33
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et VERTEX C.et VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 34
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et VERTEX C.et VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 35
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et VERTEX C.et VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 36
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et VERTEX C.et VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 37
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et VERTEX C.et VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 38
SAT se réduit en CIRCUITSAT se réduit en CIRCUIT--SATSAT----------------------------------------------------------------------------------------------------------------------------------
• CIRCUITCIRCUIT--SATSAT
– « n » variables logiques et un circuit logique « n » variables logiques et un circuit logique construit à partir des circuits de base construit à partir des circuits de base et et , , ou ou ou ou not not ..
– La question : Le circuit peut-il rendre la valeur La question : Le circuit peut-il rendre la valeur « Vrai » pour un choix adéquat des valeurs des « Vrai » pour un choix adéquat des valeurs des variables ?variables ?
16 mars 2007 Cours de graphes 7 - Intranet 39
SAT se réduit en CIRCUITSAT se réduit en CIRCUIT--SATSAT----------------------------------------------------------------------------------------------------------------------------------
• CIRCUITCIRCUIT--SATSAT
– « n » variables logiques et un circuit logique « n » variables logiques et un circuit logique construit à partir des circuits de base construit à partir des circuits de base et et , , ou ou ou ou not not ..
– La question : Le circuit peut-il rendre la valeur La question : Le circuit peut-il rendre la valeur « Vrai » pour un choix adéquat des valeurs des « Vrai » pour un choix adéquat des valeurs des variables ?variables ?
CIRCUITCIRCUIT--SAT est bien dans SAT est bien dans NPNP , car si on nous , car si on nousdonne une solution nous sommes capables dedonne une solution nous sommes capables de
vérifier que c’en est bien une en tempsvérifier que c’en est bien une en tempspolynômial et de façon déterministe !polynômial et de façon déterministe !
16 mars 2007 Cours de graphes 7 - Intranet 40
SAT se réduit en CIRCUITSAT se réduit en CIRCUIT--SATSAT----------------------------------------------------------------------------------------------------------------------------------
• CIRCUITCIRCUIT--SATSAT
– « n » variables logiques et un circuit logique construit à « n » variables logiques et un circuit logique construit à partir des circuits de base partir des circuits de base et et , , ou ou ou ou not not ..
– La question : Le circuit peut-il rendre la valeur « Vrai » La question : Le circuit peut-il rendre la valeur « Vrai » pour un choix adéquat des valeurs des variables ?pour un choix adéquat des valeurs des variables ?
• La réduction :La réduction :
– Nous allons traduire une formule logique de SAT en un Nous allons traduire une formule logique de SAT en un circuit de circuit de CIRCUITCIRCUIT--SATSAT qui donne les mêmes résultats ! qui donne les mêmes résultats !
16 mars 2007 Cours de graphes 7 - Intranet 41
SAT se réduit en CIRCUITSAT se réduit en CIRCUIT--SATSAT----------------------------------------------------------------------------------------------------------------------------------
• La réduction :La réduction :
– Variable 3Variable 3--SAT SAT --> variable CIRCUIT> variable CIRCUIT--SAT.SAT.
16 mars 2007 Cours de graphes 7 - Intranet 42
SAT se réduit en CIRCUITSAT se réduit en CIRCUIT--SATSAT----------------------------------------------------------------------------------------------------------------------------------
• La réduction :La réduction :
– Variable 3Variable 3--SAT SAT --> variable CIRCUIT> variable CIRCUIT--SAT.SAT.
– x x --> > xx
16 mars 2007 Cours de graphes 7 - Intranet 43
SAT se réduit en CIRCUITSAT se réduit en CIRCUIT--SATSAT----------------------------------------------------------------------------------------------------------------------------------
• La réduction :La réduction :
– Variable 3Variable 3--SAT SAT --> variable CIRCUIT> variable CIRCUIT--SAT.SAT.
– x x --> > xx
– ( a v b v . . . v z ) ( a v b v . . . v z ) --> > aa
bb . . . . . .. . . . . .
zz
. . .. . .
16 mars 2007 Cours de graphes 7 - Intranet 44
SAT se réduit en CIRCUITSAT se réduit en CIRCUIT--SATSAT----------------------------------------------------------------------------------------------------------------------------------
• La réduction :La réduction :
– Variable 3Variable 3--SAT SAT --> variable CIRCUIT> variable CIRCUIT--SAT.SAT.
– x x --> > xx
– ( a v b v . . . v z ) ( a v b v . . . v z ) --> > aa
bb . . . . . .. . . . . .
zz
– ( a b . . . z ) ( a b . . . z ) -->> aa bb . . . . .. . . . . ..
zz
vvvv vv
. . .. . .
. . .. . .
16 mars 2007 Cours de graphes 7 - Intranet 45
SAT se réduit en CIRCUITSAT se réduit en CIRCUIT--SATSAT----------------------------------------------------------------------------------------------------------------------------------
• La réduction :La réduction :
– Variable 3Variable 3--SAT SAT --> variable CIRCUIT> variable CIRCUIT--SAT.SAT.
– x x --> > xx
– ( a v b v . . . v z ) ( a v b v . . . v z ) --> > aa
bb . . . . . .. . . . . .
zz
– ( a b . . . z ) ( a b . . . z ) -->> aa bb . . . . .. . . . . ..
zz
vvvv vv
. . .. . .
. . .. . .
16 mars 2007 Cours de graphes 7 - Intranet 46
SAT se réduit en CIRCUITSAT se réduit en CIRCUIT--SATSAT----------------------------------------------------------------------------------------------------------------------------------
• La réduction :La réduction :
– Variable 3Variable 3--SAT SAT --> variable CIRCUIT> variable CIRCUIT--SAT.SAT.
– x x --> > xx
– ( a v b v . . . v z ) ( a v b v . . . v z ) --> > aa
bb . . . . . .. . . . . .
zz
– ( a b . . . z ) ( a b . . . z ) -->> aa bb . . . . .. . . . . ..
zz
vvvv vv
. . .. . .La réductionLa réductionest dans est dans PP ! !
. . .. . .
16 mars 2007 Cours de graphes 7 - Intranet 47
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et VERTEX C.et VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 48
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
• Une formule SAT est une formule de profondeur Une formule SAT est une formule de profondeur quelconque qui comporte des littéraux ou leurs quelconque qui comporte des littéraux ou leurs négations ainsi que des conjonctions et des négations ainsi que des conjonctions et des disjonctions binaires.disjonctions binaires.
( ( x v ( ( x v y ) v ( ( y ( z v t ) ) y ) v ( ( y ( z v t ) ) x ) ) x ) )
vv vv
16 mars 2007 Cours de graphes 7 - Intranet 49
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
• Une formule SAT est une formule de profondeur Une formule SAT est une formule de profondeur quelconque qui comporte des littéraux ou leurs négations quelconque qui comporte des littéraux ou leurs négations ainsi que des conjonctions et des disjonctions binaires.ainsi que des conjonctions et des disjonctions binaires.
( ( x v ( ( x v y ) v ( ( y ( z v t ) ) y ) v ( ( y ( z v t ) ) x ) ) x ) )
• Une formule 3Une formule 3--SAT FNC (forme normale conjonctive) est SAT FNC (forme normale conjonctive) est une formule qui comporte une conjonction n-aire composée une formule qui comporte une conjonction n-aire composée de disjonctions avec trois littéraux ou leurs négations.de disjonctions avec trois littéraux ou leurs négations.
( a v ( a v b v c ) ( a v d v e ) . . . ( b v c ) ( a v d v e ) . . . ( d v c v e d v c v e ))
vv vv
vv vv vv
16 mars 2007 Cours de graphes 7 - Intranet 50
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
• Une formule SAT est une formule de profondeur Une formule SAT est une formule de profondeur quelconque qui comporte des littéraux ou leurs négations quelconque qui comporte des littéraux ou leurs négations ainsi que des conjonctions et des disjonctions binaires.ainsi que des conjonctions et des disjonctions binaires.
( ( x v ( ( x v y ) v ( ( y ( z v t ) ) y ) v ( ( y ( z v t ) ) x ) ) x ) )
• Une formule 3Une formule 3--SAT FNC (forme normale conjonctive) est SAT FNC (forme normale conjonctive) est une formule qui comporte une conjonction n-aire composée une formule qui comporte une conjonction n-aire composée de disjonctions avec trois littéraux ou leurs négations.de disjonctions avec trois littéraux ou leurs négations.
( a v ( a v b v c ) ( a v d v e ) . . . ( b v c ) ( a v d v e ) . . . ( d v c v e d v c v e ))
vv vv
vv vv vv
33--SAT FNC est bien dans SAT FNC est bien dans NPNP , car si on nous donne une , car si on nous donne unesolution nous sommes capables de vérifier que c’en estsolution nous sommes capables de vérifier que c’en est
bien une en temps polynômial et de façon déterministe !bien une en temps polynômial et de façon déterministe !
16 mars 2007 Cours de graphes 7 - Intranet 51
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
• Une formule SAT est une formule de profondeur quelconque qui Une formule SAT est une formule de profondeur quelconque qui comporte des littéraux ou leurs négations ainsi que des comporte des littéraux ou leurs négations ainsi que des conjonctions et des disjonctions binaires.conjonctions et des disjonctions binaires.
( ( x v ( ( x v y ) v ( ( y ( z v t ) ) y ) v ( ( y ( z v t ) ) x ) ) x ) )
• Une formule 3Une formule 3--SAT FNC (forme normale conjonctive) est une SAT FNC (forme normale conjonctive) est une formule qui comporte une conjonction n-aire composée de formule qui comporte une conjonction n-aire composée de disjonctions avec trois littéraux ou leurs négations.disjonctions avec trois littéraux ou leurs négations.
( a v ( a v b v c ) ( a v d v e ) . . . ( b v c ) ( a v d v e ) . . . ( d v c v e ) d v c v e )
• Nous allons « aplatir » notre formule SAT en une formule 3Nous allons « aplatir » notre formule SAT en une formule 3--SAT SAT FNC.FNC.
vv
vv vv
vv vv
16 mars 2007 Cours de graphes 7 - Intranet 52
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
• A une variable SAT nous associons une variable 3A une variable SAT nous associons une variable 3--SAT SAT FNC.FNC.
16 mars 2007 Cours de graphes 7 - Intranet 53
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
• A une variable SAT nous associons une variable 3A une variable SAT nous associons une variable 3--SAT SAT FNC.FNC.
• A une formule SAT de la forme ( A op B ) nous A une formule SAT de la forme ( A op B ) nous associons une nouvelle variable y pour laquelle nous associons une nouvelle variable y pour laquelle nous affirmons queaffirmons que
16 mars 2007 Cours de graphes 7 - Intranet 54
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
• A une variable SAT nous associons une variable 3A une variable SAT nous associons une variable 3--SAT SAT FNC.FNC.
• A une formule SAT de la forme ( A op B ) nous A une formule SAT de la forme ( A op B ) nous associons une nouvelle variable y pour laquelle nous associons une nouvelle variable y pour laquelle nous affirmons queaffirmons que
– y est vraiey est vraie
yy
16 mars 2007 Cours de graphes 7 - Intranet 55
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
• A une variable SAT nous associons une variable 3A une variable SAT nous associons une variable 3--SAT SAT FNC.FNC.
• A une formule SAT de la forme ( A op B ) nous A une formule SAT de la forme ( A op B ) nous associons une nouvelle variable y pour laquelle nous associons une nouvelle variable y pour laquelle nous affirmons queaffirmons que
– y est vraiey est vraieetet– y est équivalente à ( A op B )y est équivalente à ( A op B )vvyy ( y <=> A op B )( y <=> A op B )
16 mars 2007 Cours de graphes 7 - Intranet 56
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
• A une variable SAT nous associons une variable 3A une variable SAT nous associons une variable 3--SAT FNC.SAT FNC.
• A une formule SAT de la forme ( A op B ) nous associons une A une formule SAT de la forme ( A op B ) nous associons une nouvelle variable y pour laquelle nous affirmons quenouvelle variable y pour laquelle nous affirmons que
– y est vraiey est vraieetet– y est équivalente à ( A op B )y est équivalente à ( A op B )
• Ensuite, il suffit de traduire cette équivalence en une disjonction.Ensuite, il suffit de traduire cette équivalence en une disjonction.
vvyy ( y <=> A op B )( y <=> A op B )
16 mars 2007 Cours de graphes 7 - Intranet 57
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
• Une formule de la forme ( y <=> A op B ) Une formule de la forme ( y <=> A op B ) correspond à une table de vérité avec 8 lignes. Nous correspond à une table de vérité avec 8 lignes. Nous en sélectionnons les 4 lignes qui sont fausses et nous en sélectionnons les 4 lignes qui sont fausses et nous les traduisons en une formule les traduisons en une formule qui est une qui est une disjonction de conjonctions :disjonction de conjonctions :
( y A B ) v ( ( y A B ) v ( y y A B ) v ( y A B ) v ( y A A B ) B ) v . . .v . . .
vv vv vv vv vv vv
16 mars 2007 Cours de graphes 7 - Intranet 58
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
• Une formule de la forme ( y <=> A op B ) correspond à Une formule de la forme ( y <=> A op B ) correspond à une table de vérité avec 8 lignes. Nous en sélectionnons les une table de vérité avec 8 lignes. Nous en sélectionnons les 4 lignes qui sont fausses et nous les traduisons en une 4 lignes qui sont fausses et nous les traduisons en une formule formule qui est une disjonction de conjonctions : qui est une disjonction de conjonctions :
( y A B ) v ( ( y A B ) v ( y y A B ) v ( y A B ) v ( y A A B ) v . . . B ) v . . .
• La négation de La négation de est la formule recherchée. D’après de est la formule recherchée. D’après de « De Morgan », nous obtenons :« De Morgan », nous obtenons :
( ( y v y v A v A v B ) ( y v A v B ) ( y v A v B ) ( B ) ( y v A v y v A v B ) . . .B ) . . .
vv
vv vv vv vv vv vv
vv vv
16 mars 2007 Cours de graphes 7 - Intranet 59
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
• Une formule de la forme ( y <=> A op B ) correspond à Une formule de la forme ( y <=> A op B ) correspond à une table de vérité avec 8 lignes. Nous en sélectionnons les une table de vérité avec 8 lignes. Nous en sélectionnons les 4 lignes qui sont fausses et nous les traduisons en une 4 lignes qui sont fausses et nous les traduisons en une formule formule qui est une disjonction de conjonctions : qui est une disjonction de conjonctions :
( y A B ) v ( ( y A B ) v ( y y A B ) v ( y A B ) v ( y A A B ) v . . . B ) v . . .
• La négation de La négation de est la formule recherchée. D’après de est la formule recherchée. D’après de « De Morgan », nous obtenons :« De Morgan », nous obtenons :
( ( y v y v A v A v B ) ( y v A v B ) ( y v A v B ) ( B ) ( y v A v y v A v B ) . . .B ) . . .
vv
vv vv vv vv vv vv
vv vv
16 mars 2007 Cours de graphes 7 - Intranet 60
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
• Une formule de la forme ( y <=> A op B ) correspond à une Une formule de la forme ( y <=> A op B ) correspond à une table de vérité avec 8 lignes. Nous en sélectionnons les lignes qui table de vérité avec 8 lignes. Nous en sélectionnons les lignes qui sont fausses et nous les traduisons en une formule sont fausses et nous les traduisons en une formule qui est une qui est une disjonction de conjonctions :disjonction de conjonctions :
( y A B ) v ( ( y A B ) v ( y y A B ) v ( y A B ) v ( y A A B ) B )
• La négation de La négation de est la formule recherchée. D’après de « De est la formule recherchée. D’après de « De Morgan », nous obtenons :Morgan », nous obtenons :
( ( y v y v A v A v B ) ( y v A v B ) ( y v A v B ) ( B ) ( y v A v B ) y v A v B )
• La même approche reste vraie pour tous les opérateurs binaires, La même approche reste vraie pour tous les opérateurs binaires, comme et , ou , => , <=> , . . .comme et , ou , => , <=> , . . .
vv
vv vv vv vv vv vv
vv
16 mars 2007 Cours de graphes 7 - Intranet 61
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
U NU N
E X E M P L EE X E M P L E
16 mars 2007 Cours de graphes 7 - Intranet 62
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x => x ) x ) v x )( ( ( x => x ) x ) v x )vv
22 33 22 11
16 mars 2007 Cours de graphes 7 - Intranet 63
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x ( ( ( x =>=> x ) x ) x ) x ) vv x ) x )vv
22 33 22 11
vv
xx11
vv
xx22=>=>
xx33
xx22
16 mars 2007 Cours de graphes 7 - Intranet 64
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x ( ( ( x =>=> x ) x ) x ) x ) vv x ) x )vv
22 33 22 11
vv
xx11
vv
xx22=>=>
xx33
xx22
yy11
yy22
yy33
16 mars 2007 Cours de graphes 7 - Intranet 65
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x ( ( ( x =>=> x ) x ) x ) x ) vv x ) x )vv
22 33 22 11
vv
xx11
vv
xx22=>=>
xx33
xx22
yy11
yy22
yy33
yy11
vv
( ( yy <=> ( y v x ) ) <=> ( y v x ) )11 22 11
vv
. . .. . .
16 mars 2007 Cours de graphes 7 - Intranet 66
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x ( ( ( x =>=> x ) x ) x ) x ) vv x ) x )vv
22 33 22 11
vv
xx11
vv
xx22=>=>
xx33
xx22
yy11
yy22
yy33
yy11
vv
( ( yy <=> ( y v x ) ) <=> ( y v x ) )11 22 11
vv
. . .. . .
16 mars 2007 Cours de graphes 7 - Intranet 67
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x ( ( ( x =>=> x ) x ) x ) x ) vv x ) x )vv
22 33 22 11
vv
xx11
vv
xx22=>=>
xx33
xx22
yy11
yy22
yy33
yy11
vv
( ( yy <=> ( <=> ( yy v x ) ) v x ) )11
vv
vv
. . .. . .
( ( yy <=> ( y x ) ) <=> ( y x ) )22 33 22
vv
22 11
16 mars 2007 Cours de graphes 7 - Intranet 68
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x ( ( ( x =>=> x ) x ) x ) x ) vv x ) x )vv
22 33 22 11
vv
xx11
vv
xx22=>=>
xx33
xx22
yy11
yy22
yy33
yy11
vv
( ( yy <=> ( <=> ( yy v x ) ) v x ) )11
vv
vv
( ( yy <=> ( <=> ( yy x ) ) x ) )22
( ( yy <=> ( x => x ) ) <=> ( x => x ) )33 22 33
22 11
33 22
vv
16 mars 2007 Cours de graphes 7 - Intranet 69
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x ( ( ( x =>=> x ) x ) x ) x ) vv x ) x )vv
22 33 22 11
vv
xx11
vv
xx22=>=>
xx33
xx22
yy11
yy22
yy33
yy11
vv
( ( yy <=> ( <=> ( yy v x ) ) v x ) )11
vv
vv
( ( yy <=> ( <=> ( yy x ) ) x ) )22
( ( yy <=> ( x => x ) ) <=> ( x => x ) )33 22 33
22 11
33 22
vv
16 mars 2007 Cours de graphes 7 - Intranet 70
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x ( ( ( x =>=> x ) x ) x ) x ) vv x ) x )vv
22 33 22 11
yy11
vv
( ( yy <=> ( <=> ( yy v x ) ) v x ) )11
vv
vv
( ( yy <=> ( <=> ( yy x ) ) x ) )22
( ( yy <=> ( x => x ) ) <=> ( x => x ) )33 22 33
22 11
33 22
vv
yy33
xx22
xx33
. . .. . .
16 mars 2007 Cours de graphes 7 - Intranet 71
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x ( ( ( x =>=> x ) x ) x ) x ) vv x ) x )vv
22 33 22 11
yy11
vv
( ( yy <=> ( <=> ( yy v x ) ) v x ) )11
vv
vv
( ( yy <=> ( <=> ( yy x ) ) x ) )22
( ( yy <=> ( x => x ) ) <=> ( x => x ) )33 22 33
22 11
33 22
vv
yy33
xx22
xx33
. . .. . .
0 0 0 00 0 0 0
0 0 1 00 0 1 0
0 1 0 10 1 0 1
0 1 1 00 1 1 0
1 0 0 11 0 0 1
1 0 1 11 0 1 1
1 1 0 01 1 0 0
1 1 1 11 1 1 1
16 mars 2007 Cours de graphes 7 - Intranet 72
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x ( ( ( x =>=> x ) x ) x ) x ) vv x ) x )vv
22 33 22 11
yy11
vv
( ( yy <=> ( <=> ( yy v x ) ) v x ) )11
vv
vv
( ( yy <=> ( <=> ( yy x ) ) x ) )22
( ( yy <=> ( x => x ) ) <=> ( x => x ) )33 22 33
22 11
33 22
vv
yy33
xx22
xx33
. . .. . .
0 0 0 0 0 0 00
0 0 1 0 0 1 00
0 1 0 10 1 0 1
0 1 1 0 1 1 00
1 0 0 11 0 0 1
1 0 1 11 0 1 1
1 1 0 1 1 0 00
1 1 1 11 1 1 1
= ( = ( y y x x x ) x )
v ( v ( y y x x ) v . . . x x ) v . . .
vv
33 22
vv
33
vv
33 22
vv
33
16 mars 2007 Cours de graphes 7 - Intranet 73
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x ( ( ( x =>=> x ) x ) x ) x ) vv x ) x )vv
22 33 22 11
yy11
vv
( ( yy <=> ( <=> ( yy v x ) ) v x ) )11
vv
vv
( ( yy <=> ( <=> ( yy x ) ) x ) )22
( ( yy <=> ( x => x ) ) <=> ( x => x ) )33 22 33
22 11
33 22
vv
yy33
xx22
xx33
. . .. . .
0 0 0 00 0 0 0
0 0 1 00 0 1 0
0 1 0 0 1 0 11
0 1 1 00 1 1 0
1 0 0 1 0 0 11
1 0 1 1 0 1 11
1 1 0 01 1 0 0
1 1 1 1 1 1 11
= ( y v x v x )= ( y v x v x )
( y v ( y v x v x v x ) . . .x ) . . .
vv
33 22 33
vv
33 22 33
16 mars 2007 Cours de graphes 7 - Intranet 74
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x ( ( ( x =>=> x ) x ) x ) x ) vv x ) x )vv
22 33 22 11
yy11
vv
( ( yy <=> ( <=> ( yy v x ) ) v x ) )11
vv
vv
( ( yy <=> ( <=> ( yy x ) ) x ) )22
22 11
33 22
vv
yy33
xx22
xx33
. . .. . .
0 0 0 00 0 0 0
0 0 1 00 0 1 0
0 1 0 0 1 0 11
0 1 1 00 1 1 0
1 0 0 1 0 0 11
1 0 1 1 0 1 11
1 1 0 01 1 0 0
1 1 1 1 1 1 11
( y v x v x )( y v x v x )33 22 33
vv ( y v x v ( y v x v x ) x )33 22 33
vv . . .. . .
16 mars 2007 Cours de graphes 7 - Intranet 75
SAT se réduit en 3SAT se réduit en 3--SAT FNCSAT FNC----------------------------------------------------------------------------------------------------------------------------------
( ( ( x ( ( ( x =>=> x ) x ) x ) x ) vv x ) x )vv
22 33 22 11
yy11
vv
( ( yy <=> ( <=> ( yy v x ) ) v x ) )11
vv
vv
( ( yy <=> ( <=> ( yy x ) ) x ) )22
22 11
33 22
vv
yy33
xx22
xx33
. . .. . .
0 0 0 00 0 0 0
0 0 1 00 0 1 0
0 1 0 0 1 0 11
0 1 1 00 1 1 0
1 0 0 1 0 0 11
1 0 1 1 0 1 11
1 1 0 01 1 0 0
1 1 1 1 1 1 11
( y v x v x )( y v x v x )33 22 33
vv ( y v x v ( y v x v x ) x )33 22 33
vv . . .. . .
16 mars 2007 Cours de graphes 7 - Intranet 76
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et VERTEX C.et VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 77
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et VERTEX C.et VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 78
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
• Une clique d’un graphe G = ( V , E ) est un sous-Une clique d’un graphe G = ( V , E ) est un sous-ensemble des sommets qui sont tous voisins les uns ensemble des sommets qui sont tous voisins les uns des autres !des autres !
16 mars 2007 Cours de graphes 7 - Intranet 79
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
• Une clique d’un graphe G = ( V , E ) est un sous-Une clique d’un graphe G = ( V , E ) est un sous-ensemble des sommets qui sont tous voisins les uns ensemble des sommets qui sont tous voisins les uns des autres !des autres !
Une clique deUne clique de3 sommets !3 sommets !
16 mars 2007 Cours de graphes 7 - Intranet 80
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
• Une clique d’un graphe G = ( V , E ) est un sous-Une clique d’un graphe G = ( V , E ) est un sous-ensemble des sommets qui sont tous voisins les uns ensemble des sommets qui sont tous voisins les uns des autres !des autres !
L’unique cliqueL’unique cliquede 4 sommets !de 4 sommets !
16 mars 2007 Cours de graphes 7 - Intranet 81
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
• Une clique d’un graphe G = ( V , E ) est un sous-Une clique d’un graphe G = ( V , E ) est un sous-ensemble des sommets qui sont tous voisins les uns ensemble des sommets qui sont tous voisins les uns des autres !des autres !
• Question : Y a-t-il G une clique de k sommets ?Question : Y a-t-il G une clique de k sommets ?
L’unique cliqueL’unique cliquede 4 sommets !de 4 sommets !
16 mars 2007 Cours de graphes 7 - Intranet 82
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
• Une clique d’un graphe G = ( V , E ) est un sous-ensemble des Une clique d’un graphe G = ( V , E ) est un sous-ensemble des sommets qui sont tous voisins les uns des autres !sommets qui sont tous voisins les uns des autres !
• Question : Y a-t-il G une clique de k sommets ?Question : Y a-t-il G une clique de k sommets ?
• CLIQUE est dans CLIQUE est dans NPNP car nous savons vérifier dans car nous savons vérifier dans PP si un si un ensemble de sommets est une clique ou non !ensemble de sommets est une clique ou non !
L’unique cliqueL’unique cliquede 4 sommets !de 4 sommets !
16 mars 2007 Cours de graphes 7 - Intranet 83
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
F = C . . . CF = C . . . Cvv
11
C = T v T v TC = T v T v T ii i,1i,1 T = x | T = x | x x
ppi,ji,j pp
kk
vv
i,2i,2 i,3i,3
• Soit une formule 3Soit une formule 3--SAT FNC constituée de k SAT FNC constituée de k conjonctions :conjonctions :
16 mars 2007 Cours de graphes 7 - Intranet 84
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
F = C . . . CF = C . . . Cvv
11
C = T v T v TC = T v T v T ii i,1i,1 T = x | T = x | x x
ppi,ji,j pp
kk
vv
i,2i,2 i,3i,3
• Soit une formule 3Soit une formule 3--SAT FNC constituée de k SAT FNC constituée de k conjonctions :conjonctions :
• Nous allons montrer que cette formule peut être Nous allons montrer que cette formule peut être rendue vraie si et seulement s’il existe une clique de rendue vraie si et seulement s’il existe une clique de taille k dans un certain graphe.taille k dans un certain graphe.
16 mars 2007 Cours de graphes 7 - Intranet 85
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
F = C . . . CF = C . . . Cvv
11
C = T v T v TC = T v T v T ii i,1i,1 T = x | T = x | x x
ppi,ji,j pp
kk
vv
i,2i,2 i,3i,3
• Soit une formule 3Soit une formule 3--SAT FNC constituée de k conjonctions :SAT FNC constituée de k conjonctions :
• Nous allons montrer que cette formule peut être rendue Nous allons montrer que cette formule peut être rendue vraie si et seulement s’il existe une clique de taille k dans vraie si et seulement s’il existe une clique de taille k dans un certain graphe.un certain graphe.
• CLIQUE sera donc au moins aussi difficile que 3CLIQUE sera donc au moins aussi difficile que 3--SAT FNC, SAT FNC, c’est-à-dire vraisemblablement exponentiel en général.c’est-à-dire vraisemblablement exponentiel en général.
16 mars 2007 Cours de graphes 7 - Intranet 86
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
• La construction du graphe :La construction du graphe :
• A chaque terme T nous associons un sommet.A chaque terme T nous associons un sommet.i,ji,j
16 mars 2007 Cours de graphes 7 - Intranet 87
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
• La construction du graphe :La construction du graphe :
• A chaque terme T nous associons un sommet.A chaque terme T nous associons un sommet.
• Les sommets T et T sont voisins dans le graphe Les sommets T et T sont voisins dans le graphe ssi : ssi :
– i et m sont différents,i et m sont différents,
– les termes ne sont pas la négation l’un de l’autre.les termes ne sont pas la négation l’un de l’autre.
i,ji,j
i,ji,j m,nm,n
16 mars 2007 Cours de graphes 7 - Intranet 88
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
• La construction du graphe :La construction du graphe :
• A chaque terme T nous associons un sommet.A chaque terme T nous associons un sommet.
• Les sommets T et T sont voisins dans le graphe Les sommets T et T sont voisins dans le graphe ssi : ssi :
– i et m sont différents,i et m sont différents,
– les termes ne sont pas la négation l’un de l’autre.les termes ne sont pas la négation l’un de l’autre.
i,ji,j
i,ji,j m,nm,n
16 mars 2007 Cours de graphes 7 - Intranet 89
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
• La construction du graphe :La construction du graphe :
• A chaque terme T nous associons un sommet.A chaque terme T nous associons un sommet.
• Les sommets T et T sont voisins dans le graphe Les sommets T et T sont voisins dans le graphe ssi : ssi :
– i et m sont différents,i et m sont différents,
– les termes ne sont pas la négation l’un de l’autre.les termes ne sont pas la négation l’un de l’autre.
• Cette construction est clairement déterministe et peut Cette construction est clairement déterministe et peut se faire en temps polynômial.se faire en temps polynômial.
i,ji,j
i,ji,j m,nm,n
16 mars 2007 Cours de graphes 7 - Intranet 90
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
16 mars 2007 Cours de graphes 7 - Intranet 91
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
xx11 xx
22xx
33
xx11
xx22
xx33
xx11
xx22
xx44
16 mars 2007 Cours de graphes 7 - Intranet 92
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
xx11 xx
22xx
33
xx11
xx22
xx33
xx11
xx22
xx44
En construction . . .En construction . . .
16 mars 2007 Cours de graphes 7 - Intranet 93
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
xx11 xx
22xx
33
xx11
xx22
xx33
xx11
xx22
xx44
En construction . . .En construction . . . NONNONCOMPATIBLES !COMPATIBLES !
16 mars 2007 Cours de graphes 7 - Intranet 94
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
xx11 xx
22xx
33
xx11
xx22
xx33
xx11
xx22
xx44
En construction . . .En construction . . .
16 mars 2007 Cours de graphes 7 - Intranet 95
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
xx11 xx
22xx
33
xx11
xx22
xx33
xx11
xx22
xx44
En construction . . .En construction . . .
16 mars 2007 Cours de graphes 7 - Intranet 96
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
xx11 xx
22xx
33
xx11
xx22
xx33
xx11
xx22
xx44
Le voilà !Le voilà !
16 mars 2007 Cours de graphes 7 - Intranet 97
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
• Clairement, notre formule peut être rendu vraie Clairement, notre formule peut être rendu vraie seulement si nous trouvons dans chaque terme de seulement si nous trouvons dans chaque terme de la conjonction au moins une fois la valeur vrai.la conjonction au moins une fois la valeur vrai.
• De plus, ces choix doivent être compatibles !De plus, ces choix doivent être compatibles !
16 mars 2007 Cours de graphes 7 - Intranet 98
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
• Clairement, notre formule peut être rendu vraie Clairement, notre formule peut être rendu vraie seulement si nous trouvons dans chaque terme de seulement si nous trouvons dans chaque terme de la conjonction au moins une fois la valeur vrai.la conjonction au moins une fois la valeur vrai.
• De plus, ces choix doivent être compatibles !De plus, ces choix doivent être compatibles !
16 mars 2007 Cours de graphes 7 - Intranet 99
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
• Clairement, notre formule peut être rendu vraie Clairement, notre formule peut être rendu vraie seulement si nous trouvons dans chaque terme de seulement si nous trouvons dans chaque terme de la conjonction au moins une fois la valeur vrai.la conjonction au moins une fois la valeur vrai.
• De plus, ces choix doivent être compatibles !De plus, ces choix doivent être compatibles !
16 mars 2007 Cours de graphes 7 - Intranet 100
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
• Clairement, notre formule peut être rendu vraie Clairement, notre formule peut être rendu vraie seulement si nous trouvons dans chaque terme de seulement si nous trouvons dans chaque terme de la conjonction au moins une fois la valeur vrai.la conjonction au moins une fois la valeur vrai.
• De plus, ces choix doivent être compatibles !De plus, ces choix doivent être compatibles !
16 mars 2007 Cours de graphes 7 - Intranet 101
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
• Clairement, notre formule peut être rendu vraie Clairement, notre formule peut être rendu vraie seulement si nous trouvons dans chaque terme de seulement si nous trouvons dans chaque terme de la conjonction au moins une fois la valeur vrai.la conjonction au moins une fois la valeur vrai.
• De plus, ces choix doivent être compatibles !De plus, ces choix doivent être compatibles !
16 mars 2007 Cours de graphes 7 - Intranet 102
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
• Clairement, notre formule peut être rendu vraie Clairement, notre formule peut être rendu vraie seulement si nous trouvons dans chaque terme de seulement si nous trouvons dans chaque terme de la conjonction au moins une fois la valeur vrai.la conjonction au moins une fois la valeur vrai.
• De plus, ces choix doivent être compatibles !De plus, ces choix doivent être compatibles !
• Autrement dit, ils doivent correspondre à une Autrement dit, ils doivent correspondre à une clique que nous pouvons former dans le graphe ! clique que nous pouvons former dans le graphe !
16 mars 2007 Cours de graphes 7 - Intranet 103
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
• Clairement, notre formule peut être rendu vraie Clairement, notre formule peut être rendu vraie seulement si nous trouvons dans chaque terme de seulement si nous trouvons dans chaque terme de la conjonction au moins une fois la valeur vrai.la conjonction au moins une fois la valeur vrai.
• De plus, ces choix doivent être compatibles !De plus, ces choix doivent être compatibles !
• Autrement dit, ils doivent correspondre à une Autrement dit, ils doivent correspondre à une clique que nous pouvons former dans le graphe ! clique que nous pouvons former dans le graphe !
• Rendre vraie la formule ou trouver une clique Rendre vraie la formule ou trouver une clique dans le graphe sont donc des problèmes de même dans le graphe sont donc des problèmes de même difficulté ! ! !difficulté ! ! !
16 mars 2007 Cours de graphes 7 - Intranet 104
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
xx11 xx
22xx
33
xx11
xx22
xx33
xx11
xx22
xx44
Une solution !Une solution !
16 mars 2007 Cours de graphes 7 - Intranet 105
33--SAT FNC se réduit en CLIQUESAT FNC se réduit en CLIQUE----------------------------------------------------------------------------------------------------------------------------------
( x v ( x v x v x v x ) x )11 22 33
( ( x v x v x v x v x )x )11 22 33
vv ( x v x v ( x v x v x )x )11 22 44
vv
xx11 xx
22xx
33
xx11
xx22
xx33
xx11
xx22
xx44
Une autreUne autre solution !solution !
16 mars 2007 Cours de graphes 7 - Intranet 106
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et VERTEX C.et VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 107
CLIQUE se réduit en VERTEX COVERCLIQUE se réduit en VERTEX COVER----------------------------------------------------------------------------------------------------------------------------------
• Nous nous donnons un graphe G = ( V , E ) avec Nous nous donnons un graphe G = ( V , E ) avec n sommets et une constante naturelle k .n sommets et une constante naturelle k .
• Question : Pouvons-nous trouver un sous-Question : Pouvons-nous trouver un sous-ensemble V’ d’au plus k sommets de façon à ce ensemble V’ d’au plus k sommets de façon à ce que toute arête ait au moins une extrémité dans que toute arête ait au moins une extrémité dans V’ ?V’ ?
16 mars 2007 Cours de graphes 7 - Intranet 108
CLIQUE se réduit en VERTEX COVERCLIQUE se réduit en VERTEX COVER----------------------------------------------------------------------------------------------------------------------------------
• Nous nous donnons un graphe G = ( V , E ) avec Nous nous donnons un graphe G = ( V , E ) avec n sommets et une constante naturelle k .n sommets et une constante naturelle k .
• Question : Pouvons-nous trouver un sous-Question : Pouvons-nous trouver un sous-ensemble V’ d’au plus k sommets de façon à ce ensemble V’ d’au plus k sommets de façon à ce que toute arête ait au moins une extrémité dans que toute arête ait au moins une extrémité dans V’ ?V’ ?
k = 2k = 2
16 mars 2007 Cours de graphes 7 - Intranet 109
CLIQUE se réduit en VERTEX COVERCLIQUE se réduit en VERTEX COVER----------------------------------------------------------------------------------------------------------------------------------
• Nous nous donnons un graphe G = ( V , E ) avec Nous nous donnons un graphe G = ( V , E ) avec n sommets et une constante naturelle k .n sommets et une constante naturelle k .
• Question : Pouvons-nous trouver un sous-Question : Pouvons-nous trouver un sous-ensemble V’ d’au plus k sommets de façon à ce ensemble V’ d’au plus k sommets de façon à ce que toute arête ait au moins une extrémité dans que toute arête ait au moins une extrémité dans V’ ?V’ ?
k = 2k = 2
OUI ! ! !OUI ! ! !
16 mars 2007 Cours de graphes 7 - Intranet 110
CLIQUE se réduit en VERTEX COVERCLIQUE se réduit en VERTEX COVER----------------------------------------------------------------------------------------------------------------------------------
• Nous nous donnons un graphe G = ( V , E ) avec Nous nous donnons un graphe G = ( V , E ) avec n sommets et une constante naturelle k .n sommets et une constante naturelle k .
• Question : Pouvons-nous trouver un sous-Question : Pouvons-nous trouver un sous-ensemble V’ d’au plus k sommets de façon à ce ensemble V’ d’au plus k sommets de façon à ce que toute arête ait au moins une extrémité dans que toute arête ait au moins une extrémité dans V’ ?V’ ?
k = 2k = 2
OUI ! ! !OUI ! ! !
Les arêtes sont dansLes arêtes sont dansl’ensemble ou ellesl’ensemble ou elles
traversent la frontière !traversent la frontière !
16 mars 2007 Cours de graphes 7 - Intranet 111
CLIQUE se réduit en VERTEX COVERCLIQUE se réduit en VERTEX COVER----------------------------------------------------------------------------------------------------------------------------------
• Nous nous donnons un graphe G = ( V , E ) avec Nous nous donnons un graphe G = ( V , E ) avec n sommets et une constante naturelle k .n sommets et une constante naturelle k .
• Question : Pouvons-nous trouver un sous-Question : Pouvons-nous trouver un sous-ensemble V’ d’au plus k sommets de façon à ce ensemble V’ d’au plus k sommets de façon à ce que toute arête ait au moins une extrémité dans que toute arête ait au moins une extrémité dans V’ ?V’ ?
k = 2k = 2
OUI ! ! !OUI ! ! !
Les arêtes sont dansLes arêtes sont dansl’ensemble ou ellesl’ensemble ou elles
traversent la frontière !traversent la frontière !
Nous sommesNous sommescapablescapablesde vérifierde vérifierune solution enune solution entemps polynômialtemps polynômialet déterministe ! ! !et déterministe ! ! !
16 mars 2007 Cours de graphes 7 - Intranet 112
CLIQUE se réduit en VERTEX COVERCLIQUE se réduit en VERTEX COVER----------------------------------------------------------------------------------------------------------------------------------
• Pourquoi est-ce un VERTEX COVER ?Pourquoi est-ce un VERTEX COVER ?
16 mars 2007 Cours de graphes 7 - Intranet 113
CLIQUE se réduit en VERTEX COVERCLIQUE se réduit en VERTEX COVER----------------------------------------------------------------------------------------------------------------------------------
• Pourquoi est-ce un VERTEX COVER ?Pourquoi est-ce un VERTEX COVER ?
• C’en est un parce que les sommets en dehors de C’en est un parce que les sommets en dehors de V’ n’ont aucune arête en commun ! ! !V’ n’ont aucune arête en commun ! ! !
16 mars 2007 Cours de graphes 7 - Intranet 114
CLIQUE se réduit en VERTEX COVERCLIQUE se réduit en VERTEX COVER----------------------------------------------------------------------------------------------------------------------------------
• Pourquoi est-ce un VERTEX COVER ?Pourquoi est-ce un VERTEX COVER ?
• C’en est un parce que les sommets en dehors de C’en est un parce que les sommets en dehors de V’ n’ont aucune arête en commun ! ! !V’ n’ont aucune arête en commun ! ! !
• Autrement dit, les arêtes absentes comportent Autrement dit, les arêtes absentes comportent une clique de taille | V | – | V’ | , c’est-à-dire n – k une clique de taille | V | – | V’ | , c’est-à-dire n – k ..
16 mars 2007 Cours de graphes 7 - Intranet 115
CLIQUE se réduit en VERTEX COVERCLIQUE se réduit en VERTEX COVER----------------------------------------------------------------------------------------------------------------------------------
• Pourquoi est-ce un VERTEX COVER ?Pourquoi est-ce un VERTEX COVER ?
• C’en est un parce que les sommets en dehors de C’en est un parce que les sommets en dehors de V’ n’ont aucune arête en commun ! ! !V’ n’ont aucune arête en commun ! ! !
• Autrement dit, les arêtes absentes comportent Autrement dit, les arêtes absentes comportent une clique de taille | V | – | V’ | , c’est-à-dire n – k une clique de taille | V | – | V’ | , c’est-à-dire n – k ..
Considérons leConsidérons legraphe G’ quigraphe G’ qui
contient les arêtescontient les arêtesabsentes de G !absentes de G !
16 mars 2007 Cours de graphes 7 - Intranet 116
CLIQUE se réduit en VERTEX COVERCLIQUE se réduit en VERTEX COVER----------------------------------------------------------------------------------------------------------------------------------
• Pourquoi est-ce un VERTEX COVER ?Pourquoi est-ce un VERTEX COVER ?
• C’en est un parce que les sommets en dehors de C’en est un parce que les sommets en dehors de V’ n’ont aucune arête en commun ! ! !V’ n’ont aucune arête en commun ! ! !
• Autrement dit, les arêtes absentes comportent Autrement dit, les arêtes absentes comportent une clique de taille | V | – | V’ | , c’est-à-dire n – k une clique de taille | V | – | V’ | , c’est-à-dire n – k ..
Considérons leConsidérons legraphe G’ quigraphe G’ qui
contient les arêtescontient les arêtesabsentes de G !absentes de G !
G’ possède alorsG’ possède alorsune clique deune clique detaille n – k .taille n – k .
16 mars 2007 Cours de graphes 7 - Intranet 117
CLIQUE se réduit en VERTEX COVERCLIQUE se réduit en VERTEX COVER----------------------------------------------------------------------------------------------------------------------------------
• Pour un graphe avec n sommets, il est équivalent Pour un graphe avec n sommets, il est équivalent de de
– de trouver un VERTEX COVER de taille k oude trouver un VERTEX COVER de taille k ou
– de trouver une CLIQUE de taille n – k dans le de trouver une CLIQUE de taille n – k dans le graphe complémentaire.graphe complémentaire.
Considérons leConsidérons legraphe G’ quigraphe G’ qui
contient les arêtescontient les arêtesabsentes de G !absentes de G !
G’ possède alorsG’ possède alorsune clique deune clique detaille n – k .taille n – k .
16 mars 2007 Cours de graphes 7 - Intranet 118
CLIQUE se réduit en VERTEX COVERCLIQUE se réduit en VERTEX COVER----------------------------------------------------------------------------------------------------------------------------------
• Pour un graphe avec n sommets, il est équivalent Pour un graphe avec n sommets, il est équivalent de de
– de trouver un VERTEX COVER de taille k oude trouver un VERTEX COVER de taille k ou
– de trouver une CLIQUE de taille n – k dans le de trouver une CLIQUE de taille n – k dans le graphe complémentaire.graphe complémentaire.
Considérons leConsidérons legraphe G’ quigraphe G’ qui
contient les arêtescontient les arêtesabsentes de G !absentes de G !
G’ possède alorsG’ possède alorsune clique deune clique detaille n – k .taille n – k .
La transformation estLa transformation estdéterministe etdéterministe etpolynômiale.polynômiale.
16 mars 2007 Cours de graphes 7 - Intranet 119
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et et VERTEX C.VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 120
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et et VERTEX C.VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 121
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons :Nous avons :
– un ensemble S d’entiers naturels non nuls,un ensemble S d’entiers naturels non nuls,
– une constante k .une constante k .
16 mars 2007 Cours de graphes 7 - Intranet 122
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons :Nous avons :
– un ensemble S d’entiers naturels non nuls,un ensemble S d’entiers naturels non nuls,
– une constante k .une constante k .
• La question est la suivante :La question est la suivante :
– Pouvons-nous trouver un sous-ensemble de S Pouvons-nous trouver un sous-ensemble de S dont la somme vaut k ?dont la somme vaut k ?
16 mars 2007 Cours de graphes 7 - Intranet 123
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons :Nous avons :
– un ensemble S d’entiers naturels non nuls,un ensemble S d’entiers naturels non nuls,
– une constante k .une constante k .
• La question est la suivante :La question est la suivante :
– Pouvons-nous trouver un sous-ensemble de S Pouvons-nous trouver un sous-ensemble de S dont la somme vaut k ?dont la somme vaut k ?
S = { 13 , 17 , 23 , 41 , 65 , 67 } et k = 105S = { 13 , 17 , 23 , 41 , 65 , 67 } et k = 105
16 mars 2007 Cours de graphes 7 - Intranet 124
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons :Nous avons :
– un ensemble S d’entiers naturels non nuls,un ensemble S d’entiers naturels non nuls,
– une constante k .une constante k .
• La question est la suivante :La question est la suivante :
– Pouvons-nous trouver un sous-ensemble de S Pouvons-nous trouver un sous-ensemble de S dont la somme vaut k ?dont la somme vaut k ?
S = { 13 , 17 , 23 , 41 , 65 , 69 } et k = 105S = { 13 , 17 , 23 , 41 , 65 , 69 } et k = 105
OUI ! ! !OUI ! ! !
16 mars 2007 Cours de graphes 7 - Intranet 125
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons :Nous avons :
– un ensemble S d’entiers naturels non nuls,un ensemble S d’entiers naturels non nuls,
– une constante k .une constante k .
• La question est la suivante :La question est la suivante :
– Pouvons-nous trouver un sous-ensemble de S Pouvons-nous trouver un sous-ensemble de S dont la somme vaut k ?dont la somme vaut k ?
S = { 13 , 17 , 23 , 41 , 65 , 69 } et k = 105S = { 13 , 17 , 23 , 41 , 65 , 69 } et k = 105
OUI ! ! !OUI ! ! !Une autre solution ! ! !Une autre solution ! ! !
16 mars 2007 Cours de graphes 7 - Intranet 126
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons :Nous avons :
– un ensemble S d’entiers naturels non nuls,un ensemble S d’entiers naturels non nuls,
– une constante k .une constante k .
• La question est la suivante :La question est la suivante :
– Pouvons-nous trouver un sous-ensemble de S Pouvons-nous trouver un sous-ensemble de S dont la somme vaut k ?dont la somme vaut k ?
• Le problème est dans Le problème est dans NPNP , car la vérification est , car la vérification est polynômiale et déterministe !polynômiale et déterministe !
16 mars 2007 Cours de graphes 7 - Intranet 127
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous considérons une matrice d’adjacence :Nous considérons une matrice d’adjacence :
16 mars 2007 Cours de graphes 7 - Intranet 128
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous considérons une matrice d’adjacence :Nous considérons une matrice d’adjacence :
44
1122
33
55
11
22
33
44
55
16 mars 2007 Cours de graphes 7 - Intranet 129
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous considérons une matrice d’adjacence :Nous considérons une matrice d’adjacence :
44
1122
33
55aa
bb
cc
dd
ee
ff
aa bb cc dd ee ff
11
22
33
44
55
16 mars 2007 Cours de graphes 7 - Intranet 130
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous considérons une matrice d’adjacence :Nous considérons une matrice d’adjacence :
44
1122
33
55aa
bb
cc
dd
ee
ff
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
16 mars 2007 Cours de graphes 7 - Intranet 131
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous considérons une matrice d’adjacence :Nous considérons une matrice d’adjacence :
44
1122
33
55aa
bb
cc
dd
ee
ff
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
L’arête b est incidenteL’arête b est incidenteaux sommets 1 et 2 !aux sommets 1 et 2 !
16 mars 2007 Cours de graphes 7 - Intranet 132
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous considérons une matrice d’adjacence :Nous considérons une matrice d’adjacence :
44
33
55aa
bb
cc
dd
ee
ff
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00 Il y a deux occurrencesIl y a deux occurrencesde 1 sur chaque colonne !de 1 sur chaque colonne !
1122
L’arête b est incidenteL’arête b est incidenteaux sommets 1 et 2 !aux sommets 1 et 2 !
16 mars 2007 Cours de graphes 7 - Intranet 133
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous considérons une matrice d’adjacence :Nous considérons une matrice d’adjacence :
44
1122
33
55aa
bb
cc
dd
ee
ff
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
11
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
16 mars 2007 Cours de graphes 7 - Intranet 134
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous considérons une matrice d’adjacence :Nous considérons une matrice d’adjacence :
44
1122
33
55aa
bb
cc
dd
ee
ff
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
11
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
16 mars 2007 Cours de graphes 7 - Intranet 135
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
---- aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
11
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
16 mars 2007 Cours de graphes 7 - Intranet 136
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous rajoutons uneNous rajoutons une matrice identité !matrice identité !
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
11
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
0000 00 00 00 110000 00 00 11 00
0000 00 11 00 00
0000 11 00 00 00
1100 00 00 00 00
0011 00 00 00 00
16 mars 2007 Cours de graphes 7 - Intranet 137
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous rajoutons uneNous rajoutons une matrice identité !matrice identité !
• Nous rajoutons uneNous rajoutons une colonne au début !colonne au début !
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
16 mars 2007 Cours de graphes 7 - Intranet 138
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous rajoutons uneNous rajoutons une matrice identité !matrice identité !
• Nous rajoutons uneNous rajoutons une colonne au début !colonne au début !
• A lire en base 4, ilA lire en base 4, il n’y a pas de retenue !n’y a pas de retenue !
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
++
33 33 33 33 3333| V || V |
16 mars 2007 Cours de graphes 7 - Intranet 139
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous rajoutons uneNous rajoutons une matrice identité !matrice identité !
• Nous rajoutons uneNous rajoutons une colonne au début !colonne au début !
• A lire en base 4, ilA lire en base 4, il n’y a pas de retenue !n’y a pas de retenue !
• Et les nombres sontEt les nombres sont tous différents !tous différents !
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
33 33 33 33 3333| V || V |
++= 1= 1= 4= 4
= 16= 16
= . . .= . . .
= x= x
= y= y
16 mars 2007 Cours de graphes 7 - Intranet 140
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous rajoutons uneNous rajoutons une matrice identité !matrice identité !
• Nous rajoutons uneNous rajoutons une colonne au début !colonne au début !
• A lire en base 4, ilA lire en base 4, il n’y a pas de retenue !n’y a pas de retenue !
• Et les nombres sontEt les nombres sont tous différents !tous différents !
• Chaque ligne de laChaque ligne de la matrice donne unmatrice donne un nombre de S !nombre de S !
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
33 33 33 33 3333| V || V |
++= 1= 1= 4= 4
= 16= 16
= . . .= . . .
= x= x
= y= y
16 mars 2007 Cours de graphes 7 - Intranet 141
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----Le graphe contient un VERTEX COVER de taille kLe graphe contient un VERTEX COVER de taille ksi nous pouvons choisir de telles lignes afinsi nous pouvons choisir de telles lignes afinque chaque colonne comporteque chaque colonne comporte2 occurrences de 1 !2 occurrences de 1 !
44
1122
33
55aa
bb
cc
dd
ee
ff
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
11
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
VV
16 mars 2007 Cours de graphes 7 - Intranet 142
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----Le graphe contient un VERTEX COVER de taille kLe graphe contient un VERTEX COVER de taille ksi nous pouvons choisir de telles lignes afinsi nous pouvons choisir de telles lignes afinque chaque colonne comporteque chaque colonne comporte2 occurrences de 1 !2 occurrences de 1 !
44
1122
33
55aa
bb
cc
dd
ee
ff
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
11
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
VV
{ 1 , 2 , 5 } est un VERTEX{ 1 , 2 , 5 } est un VERTEXCOVER de 3 sommets ! ! !COVER de 3 sommets ! ! !
16 mars 2007 Cours de graphes 7 - Intranet 143
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----Le graphe contient un VERTEX COVER de taille kLe graphe contient un VERTEX COVER de taille ksi nous pouvons choisir de telles lignes afinsi nous pouvons choisir de telles lignes afinque chaque colonne comporteque chaque colonne comporte2 occurrences de 1 !2 occurrences de 1 !
44
1122
33
55aa
bb
cc
dd
ee
ff
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
11
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
VV
{ 1 , 2 , 5 } est un VERTEX{ 1 , 2 , 5 } est un VERTEXCOVER de 3 sommets ! ! !COVER de 3 sommets ! ! !
16 mars 2007 Cours de graphes 7 - Intranet 144
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----Le graphe contient un VERTEX COVER de taille kLe graphe contient un VERTEX COVER de taille ksi nous pouvons choisir de telles lignes afinsi nous pouvons choisir de telles lignes afinque chaque colonne comporteque chaque colonne comporte2 occurrences de 1 !2 occurrences de 1 !
44
1122
33
55aa
bb
cc
dd
ee
ff
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
11
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
VV
{ 1 , 2 , 5 } est un VERTEX{ 1 , 2 , 5 } est un VERTEXCOVER de 3 sommets ! ! !COVER de 3 sommets ! ! !
16 mars 2007 Cours de graphes 7 - Intranet 145
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----Le graphe contient un VERTEX COVER de taille kLe graphe contient un VERTEX COVER de taille ksi nous pouvons choisir de telles lignes afinsi nous pouvons choisir de telles lignes afinque chaque colonne comporteque chaque colonne comporte2 occurrences de 1 !2 occurrences de 1 !
44
1122
33
55aa
bb
cc
dd
ee
ff
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
11
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
VV
{ 1 , 2 , 5 } est un VERTEX{ 1 , 2 , 5 } est un VERTEXCOVER de 3 sommets ! ! !COVER de 3 sommets ! ! !
16 mars 2007 Cours de graphes 7 - Intranet 146Soit k = k Soit k = k
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous rajoutons uneNous rajoutons une matrice identité !matrice identité !
• Nous rajoutons uneNous rajoutons une colonne au début !colonne au début !
• A lire en base 4, ilA lire en base 4, il n’y a pas de retenue !n’y a pas de retenue !
• Et les nombres sontEt les nombres sont tous différents !tous différents !
• Chaque ligne de laChaque ligne de la matrice donne unmatrice donne un nombre de S !nombre de S !
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
22 22 22 22 2222
++= 1= 1= 4= 4
= 16= 16
= . . .= . . .
= x= x
= y= y
SS VV
16 mars 2007 Cours de graphes 7 - Intranet 147Soit k = k Soit k = k
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous rajoutons uneNous rajoutons une matrice identité !matrice identité !
• Nous rajoutons uneNous rajoutons une colonne au début !colonne au début !
• A lire en base 4, ilA lire en base 4, il n’y a pas de retenue !n’y a pas de retenue !
• Et les nombres sontEt les nombres sont tous différents !tous différents !
• Chaque ligne de laChaque ligne de la matrice donne unmatrice donne un nombre de S !nombre de S !
aa bb cc dd ee ff
11
22
33
44
55
11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
22 22 22 22 2222
++= 1= 1= 4= 4
= 16= 16
= . . .= . . .
= x= x
= y= y
SS VV
16 mars 2007 Cours de graphes 7 - Intranet 148
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons un Nous avons un
VERTEXVERTEX
COVER de taille k COVER de taille k ssissi
nous avons un nous avons un SUBSET SUBSET
SUM de valeur k .SUM de valeur k .
VV
SS
16 mars 2007 Cours de graphes 7 - Intranet 149
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons un Nous avons un
VERTEXVERTEX
COVER de taille k COVER de taille k ssissi
nous avons un nous avons un SUBSET SUBSET
SUM de valeur k .SUM de valeur k .
VV
SS
11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
16 mars 2007 Cours de graphes 7 - Intranet 150
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons un Nous avons un
VERTEXVERTEX
COVER de taille k COVER de taille k ssissi
nous avons un nous avons un SUBSET SUBSET
SUM de valeur k .SUM de valeur k .
• Soit le VERTEX Soit le VERTEX COVER.COVER.
VV
SS
11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
k k VV
16 mars 2007 Cours de graphes 7 - Intranet 151
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons un VERTEXNous avons un VERTEX
COVER de taille k ssiCOVER de taille k ssi
nous avons un SUBSET nous avons un SUBSET
SUM de valeur k .SUM de valeur k .
• Soit le VERTEX COVER.Soit le VERTEX COVER.
• Chaque colonne comporte Chaque colonne comporte au moins une fois le au moins une fois le 1 ! ! ! Nous choisissons 1 ! ! ! Nous choisissons d’autres lignes pour d’autres lignes pour compléter à 2 !compléter à 2 !
VV
SS
11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
k = k k = k VV 22 22 22 22 2222SS
16 mars 2007 Cours de graphes 7 - Intranet 152
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons un VERTEXNous avons un VERTEX
COVER de taille k ssiCOVER de taille k ssi
nous avons un SUBSET nous avons un SUBSET
SUM de valeur k .SUM de valeur k .
• Soit le VERTEX COVER.Soit le VERTEX COVER.
• Chaque colonne comporte Chaque colonne comporte au moins une fois le au moins une fois le 1 ! ! ! Nous choisissons 1 ! ! ! Nous choisissons d’autres lignes pour d’autres lignes pour compléter à 2 !compléter à 2 !
VV
SS
11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
k = k k = k VV 22 22 22 22 2222SS
16 mars 2007 Cours de graphes 7 - Intranet 153
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons un VERTEXNous avons un VERTEX
COVER de taille k ssiCOVER de taille k ssi
nous avons un SUBSET nous avons un SUBSET
SUM de valeur k .SUM de valeur k .
• Soit le VERTEX COVER.Soit le VERTEX COVER.
• Chaque colonne comporte Chaque colonne comporte au moins une fois le au moins une fois le 1 ! ! ! Nous choisissons 1 ! ! ! Nous choisissons d’autres lignes pour d’autres lignes pour compléter à 2 !compléter à 2 !
VV
SS
11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
Nous avons une somme de k = k Nous avons une somme de k = k VV 22 22 22 22 2222SS
16 mars 2007 Cours de graphes 7 - Intranet 154
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons un VERTEXNous avons un VERTEX
COVER de taille k ssiCOVER de taille k ssi
nous avons un SUBSET nous avons un SUBSET
SUM de valeur k .SUM de valeur k .
• Soit le SUBSET SUM.Soit le SUBSET SUM.
VV
SS
11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
k = k k = k VV 22 22 22 22 2222SS
16 mars 2007 Cours de graphes 7 - Intranet 155
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----• Nous avons un VERTEXNous avons un VERTEX
COVER de taille k ssiCOVER de taille k ssi
nous avons un SUBSET nous avons un SUBSET
SUM de valeur k .SUM de valeur k .
• Soit le SUBSET SUM.Soit le SUBSET SUM.
• Nous en extrayons un Nous en extrayons un VERTEX COVER !VERTEX COVER !
VV
SS
11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
16 mars 2007 Cours de graphes 7 - Intranet 156
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----
U NU N
E X E M P L EE X E M P L E
N U M E R I Q U EN U M E R I Q U E
16 mars 2007 Cours de graphes 7 - Intranet 157
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
1 =1 =4 =4 =
16 =16 =
64 =64 =
256 =256 =
1024 =1024 =
5440 =5440 =
4356 =4356 =
4101 =4101 =
5136 =5136 =4177 =4177 =
16 mars 2007 Cours de graphes 7 - Intranet 158
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
1 =1 =4 =4 =
16 =16 =
64 =64 =
256 =256 =
1024 =1024 =
5440 =5440 =
4356 =4356 =
4101 =4101 =
5136 =5136 =4177 =4177 =
k = 15018 = 3 k = 15018 = 3 22 22 22 22 2222SS
16 mars 2007 Cours de graphes 7 - Intranet 159
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
1 =1 =4 =4 =
16 =16 =
64 =64 =
256 =256 =
1024 =1024 =
5440 =5440 =
4356 =4356 =
4101 =4101 =
5136 =5136 =4177 =4177 =
Le VERTEX COVERLe VERTEX COVER{ 1 , 2 , 5 } donne :{ 1 , 2 , 5 } donne :
544054404356435641774177
1144
161610241024
1501815018
k = 15018 = 3 k = 15018 = 3 SS 22 22 22 22 2222
16 mars 2007 Cours de graphes 7 - Intranet 160
VERTEX COVER se réduit en SUBSET SUMVERTEX COVER se réduit en SUBSET SUM--------------------------------------------------------------------------------------------------------------------------------------------------
----11
11
00
00
00
11
00
00
00
11
00
00
00
11
11
00
11
11
00
00
00
00
11
00
11
00 00 00 00 1100 00 00 11 00
00 00 11 00 00
00 11 00 00 00
11 00 00 00 00
00 00 00 00 00
11
00
00
11
00
0000
00
00
00
11
11
11
11
11
11
0000
00
00
00
00
1 =1 =4 =4 =
16 =16 =
64 =64 =
256 =256 =
1024 =1024 =
5440 =5440 =
4356 =4356 =
4101 =4101 =
5136 =5136 =4177 =4177 =
Le VERTEX COVERLe VERTEX COVER{ 2 , 4 , 5 } donne :{ 2 , 4 , 5 } donne :
435643565136513641774177
1144
6464256256
10241024
1501815018
k = 15018 = 3 k = 15018 = 3 SS 22 22 22 22 2222
16 mars 2007 Cours de graphes 7 - Intranet 161
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et VERTEX C.et VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 162
SUBSET SUM se réduit en 0-1 LINEAR PROG.SUBSET SUM se réduit en 0-1 LINEAR PROG.--------------------------------------------------------------------------------------------------------------------------------------------------
--------------• Nous avons un n-uplet X de variables qui Nous avons un n-uplet X de variables qui
prennent 0 ou 1 comme valeurs.prennent 0 ou 1 comme valeurs.
16 mars 2007 Cours de graphes 7 - Intranet 163
SUBSET SUM se réduit en 0-1 LINEAR PROG.SUBSET SUM se réduit en 0-1 LINEAR PROG.--------------------------------------------------------------------------------------------------------------------------------------------------
--------------• Nous avons un n-uplet X de variables qui Nous avons un n-uplet X de variables qui
prennent 0 ou 1 comme valeurs.prennent 0 ou 1 comme valeurs.
• Nous avons p inéquations d’inconnue X :Nous avons p inéquations d’inconnue X :
a x + . . . + a x <= ba x + . . . + a x <= b1,11,1 11 1,n1,n nn 11
a x + . . . + a x <= ba x + . . . + a x <= bp,1p,1 11 p,np,n nn pp
. . .. . .
16 mars 2007 Cours de graphes 7 - Intranet 164
SUBSET SUM se réduit en 0-1 LINEAR PROG.SUBSET SUM se réduit en 0-1 LINEAR PROG.--------------------------------------------------------------------------------------------------------------------------------------------------
--------------• Nous avons un n-uplet X de variables qui Nous avons un n-uplet X de variables qui
prennent 0 ou 1 comme valeurs.prennent 0 ou 1 comme valeurs.
• Nous avons p inéquations d’inconnue X :Nous avons p inéquations d’inconnue X :
a x + . . . + a x <= ba x + . . . + a x <= b1,11,1 11 1,n1,n nn 11
a x + . . . + a x <= ba x + . . . + a x <= bp,1p,1 11 p,np,n nn pp
. . .. . .Sous formeSous formematricielle :matricielle :
A X <= BA X <= B
16 mars 2007 Cours de graphes 7 - Intranet 165
SUBSET SUM se réduit en 0-1 LINEAR PROG.SUBSET SUM se réduit en 0-1 LINEAR PROG.--------------------------------------------------------------------------------------------------------------------------------------------------
--------------• Nous avons un n-uplet X de variables qui Nous avons un n-uplet X de variables qui
prennent 0 ou 1 comme valeurs.prennent 0 ou 1 comme valeurs.
• Nous avons p inéquations d’inconnue X :Nous avons p inéquations d’inconnue X :
• La question : Pouvons-nous trouver un vecteur La question : Pouvons-nous trouver un vecteur X qui satisfait toutes les inéquations ?X qui satisfait toutes les inéquations ?
a x + . . . + a x <= ba x + . . . + a x <= b1,11,1 11 1,n1,n nn 11
a x + . . . + a x <= ba x + . . . + a x <= bp,1p,1 11 p,np,n nn pp
. . .. . .Sous formeSous formematricielle :matricielle :
A X <= BA X <= B
16 mars 2007 Cours de graphes 7 - Intranet 166
SUBSET SUM se réduit en 0-1 LINEAR PROG.SUBSET SUM se réduit en 0-1 LINEAR PROG.--------------------------------------------------------------------------------------------------------------------------------------------------
--------------• Nous avons un n-uplet X de variables qui prennent 0 Nous avons un n-uplet X de variables qui prennent 0
ou 1 comme valeurs.ou 1 comme valeurs.
• Nous avons p inéquations d’inconnue X :Nous avons p inéquations d’inconnue X :
• La question : Pouvons-nous trouver un vecteur X qui La question : Pouvons-nous trouver un vecteur X qui satisfait toutes les inéquations ?satisfait toutes les inéquations ?
• Le problème est bien dans Le problème est bien dans NPNP ! !
a x + . . . + a x <= ba x + . . . + a x <= b1,11,1 11 1,n1,n nn 11
a x + . . . + a x <= ba x + . . . + a x <= bp,1p,1 11 p,np,n nn pp
. . .. . .Sous formeSous formematricielle :matricielle :
A X <= BA X <= B
16 mars 2007 Cours de graphes 7 - Intranet 167
SUBSET SUM se réduit en 0-1 LINEAR PROG.SUBSET SUM se réduit en 0-1 LINEAR PROG.--------------------------------------------------------------------------------------------------------------------------------------------------
--------------• Soit l’ensemble S = { s , . . . , s } de Soit l’ensemble S = { s , . . . , s } de
nombres et la constante k .nombres et la constante k .11 nn
16 mars 2007 Cours de graphes 7 - Intranet 168
SUBSET SUM se réduit en 0-1 LINEAR PROG.SUBSET SUM se réduit en 0-1 LINEAR PROG.--------------------------------------------------------------------------------------------------------------------------------------------------
--------------• Soit l’ensemble S = { s , . . . , s } de Soit l’ensemble S = { s , . . . , s } de
nombres et la constante k .nombres et la constante k .
• Nous construisons les deux inégalités :Nous construisons les deux inégalités :
s x + . . . + s x <= ks x + . . . + s x <= k11 11 nn nn
11 nn
– – s x – . . . – s x <= – ks x – . . . – s x <= – k11 11 nn nn
16 mars 2007 Cours de graphes 7 - Intranet 169
SUBSET SUM se réduit en 0-1 LINEAR PROG.SUBSET SUM se réduit en 0-1 LINEAR PROG.--------------------------------------------------------------------------------------------------------------------------------------------------
--------------• Soit l’ensemble S = { s , . . . , s } de Soit l’ensemble S = { s , . . . , s } de
nombres et la constante k .nombres et la constante k .
• Nous construisons les deux inégalités :Nous construisons les deux inégalités :
s x + . . . + s x <= ks x + . . . + s x <= k11 11 nn nn Celles-ciCelles-ci
équivalent àéquivalent àune égalité !une égalité !
11 nn
– – s x – . . . – s x <= – ks x – . . . – s x <= – k11 11 nn nn
==
==
16 mars 2007 Cours de graphes 7 - Intranet 170
SUBSET SUM se réduit en 0-1 LINEAR PROG.SUBSET SUM se réduit en 0-1 LINEAR PROG.--------------------------------------------------------------------------------------------------------------------------------------------------
--------------• Soit l’ensemble S = { s , . . . , s } de Soit l’ensemble S = { s , . . . , s } de
nombres et la constante k .nombres et la constante k .
• Nous construisons les deux inégalités :Nous construisons les deux inégalités :
• La transformation est dans La transformation est dans PP . .
s x + . . . + s x <= ks x + . . . + s x <= k11 11 nn nn Celles-ciCelles-ci
équivalent àéquivalent àune égalité !une égalité !
11 nn
– – s x – . . . – s x <= – ks x – . . . – s x <= – k11 11 nn nn
==
==
16 mars 2007 Cours de graphes 7 - Intranet 171
SUBSET SUM se réduit en 0-1 LINEAR PROG.SUBSET SUM se réduit en 0-1 LINEAR PROG.--------------------------------------------------------------------------------------------------------------------------------------------------
--------------• Soit l’ensemble S = { s , . . . , s } de nombres Soit l’ensemble S = { s , . . . , s } de nombres
et la constante k .et la constante k .
• Nous construisons les deux inégalités :Nous construisons les deux inégalités :
• La transformation est dans La transformation est dans PP . .
• Trivial : k peut être obtenue comme somme de Trivial : k peut être obtenue comme somme de nombres de S , si et seulement si, le système de nombres de S , si et seulement si, le système de programmation 0–1 admet une solution. programmation 0–1 admet une solution.
s x + . . . + s x <= ks x + . . . + s x <= k11 11 nn nn Celles-ciCelles-ci
équivalent àéquivalent àune égalité !une égalité !
11 nn
– – s x – . . . – s x <= – ks x – . . . – s x <= – k11 11 nn nn
==
==
16 mars 2007 Cours de graphes 7 - Intranet 172
Réductions polynômialesRéductions polynômiales----------------------------------------------------------------------------------------------------------------------------------
• Nous construirons les réductions polynômiales Nous construirons les réductions polynômiales suivantes :suivantes :
PPSATSAT
PP
CIRCUITCIRCUIT--SATSAT
PP33--SAT FNCSAT FNC
SUBSET SUMSUBSET SUM
CLIQUECLIQUE VERTEX COVERVERTEX COVERPP
et VERTEX C.et VERTEX C.PP PP
PP SET PARTITIONSET PARTITION
00--1 LINEAR PROG.1 LINEAR PROG.
16 mars 2007 Cours de graphes 7 - Intranet 173
SUBSET SUM se réduit en SET PARTITIONSUBSET SUM se réduit en SET PARTITION--------------------------------------------------------------------------------------------------------------------------------------------------
--------• Le problème SET PARTITION consiste à savoir si un Le problème SET PARTITION consiste à savoir si un
ensemble S de nombres naturels peut être ensemble S de nombres naturels peut être décomposé en deux sous-ensembles de nombres décomposé en deux sous-ensembles de nombres de sommes égales. de sommes égales.
16 mars 2007 Cours de graphes 7 - Intranet 174
SUBSET SUM se réduit en SET PARTITIONSUBSET SUM se réduit en SET PARTITION--------------------------------------------------------------------------------------------------------------------------------------------------
--------
S = { 17 , 37 , 48 , 70 , 76 }S = { 17 , 37 , 48 , 70 , 76 }
• Le problème SET PARTITION consiste à savoir si un Le problème SET PARTITION consiste à savoir si un ensemble S de nombres naturels peut être ensemble S de nombres naturels peut être décomposé en deux sous-ensembles de nombres décomposé en deux sous-ensembles de nombres de sommes égales. de sommes égales.
16 mars 2007 Cours de graphes 7 - Intranet 175
SUBSET SUM se réduit en SET PARTITIONSUBSET SUM se réduit en SET PARTITION--------------------------------------------------------------------------------------------------------------------------------------------------
--------
S = { S = { 1717 , , 3737 , , 4848 , , 7070 , , 7676 } }
OUI ! ! !OUI ! ! !
• Le problème SET PARTITION consiste à savoir si un Le problème SET PARTITION consiste à savoir si un ensemble S de nombres naturels peut être ensemble S de nombres naturels peut être décomposé en deux sous-ensembles de nombres décomposé en deux sous-ensembles de nombres de sommes égales. de sommes égales.
16 mars 2007 Cours de graphes 7 - Intranet 176
SUBSET SUM se réduit en SET PARTITIONSUBSET SUM se réduit en SET PARTITION--------------------------------------------------------------------------------------------------------------------------------------------------
--------
S = { S = { 1717 , , 3737 , , 4848 , , 7070 , , 7676 } }
OUI ! ! !OUI ! ! !
• Le problème SET PARTITION consiste à savoir si un Le problème SET PARTITION consiste à savoir si un ensemble S de nombres naturels peut être ensemble S de nombres naturels peut être décomposé en deux sous-ensembles de nombres décomposé en deux sous-ensembles de nombres de sommes égales. de sommes égales.
• Le problème est bien dans Le problème est bien dans NPNP ! !
16 mars 2007 Cours de graphes 7 - Intranet 177
SUBSET SUM se réduit en SET PARTITIONSUBSET SUM se réduit en SET PARTITION--------------------------------------------------------------------------------------------------------------------------------------------------
--------• Soit l’ensemble d’entiers S et la constante k Soit l’ensemble d’entiers S et la constante k
pour lesquels nous cherchons une solution à pour lesquels nous cherchons une solution à SUBSET SUM. Soit T la somme des éléments de SUBSET SUM. Soit T la somme des éléments de S .S .
16 mars 2007 Cours de graphes 7 - Intranet 178
SUBSET SUM se réduit en SET PARTITIONSUBSET SUM se réduit en SET PARTITION--------------------------------------------------------------------------------------------------------------------------------------------------
--------• Soit l’ensemble d’entiers S et la constante k Soit l’ensemble d’entiers S et la constante k
pour lesquels nous cherchons une solution à pour lesquels nous cherchons une solution à SUBSET SUM. Soit T la somme des éléments de SUBSET SUM. Soit T la somme des éléments de S .S .
• Soit l’ensemble Z = S v { k+1 , T–k+1 } pour Soit l’ensemble Z = S v { k+1 , T–k+1 } pour lequel nous cherchons une solution à SET lequel nous cherchons une solution à SET PARTITION.PARTITION.
16 mars 2007 Cours de graphes 7 - Intranet 179
SUBSET SUM se réduit en SET PARTITIONSUBSET SUM se réduit en SET PARTITION--------------------------------------------------------------------------------------------------------------------------------------------------
--------• Soit l’ensemble d’entiers S et la constante k Soit l’ensemble d’entiers S et la constante k
pour lesquels nous cherchons une solution à pour lesquels nous cherchons une solution à SUBSET SUM. Soit T la somme des éléments de SUBSET SUM. Soit T la somme des éléments de S .S .
• Soit l’ensemble Z = S v { k+1 , T–k+1 } pour Soit l’ensemble Z = S v { k+1 , T–k+1 } pour lequel nous cherchons une solution à SET lequel nous cherchons une solution à SET PARTITION.PARTITION.
• Les deux problèmes sont équivalents.Les deux problèmes sont équivalents. La La transformationtransformation
est polynômiale et est polynômiale et déterministe.déterministe.
16 mars 2007 Cours de graphes 7 - Intranet 180
SUBSET SUM se réduit en SET PARTITIONSUBSET SUM se réduit en SET PARTITION--------------------------------------------------------------------------------------------------------------------------------------------------
--------• Soit l’ensemble d’entiers S et la constante k pour Soit l’ensemble d’entiers S et la constante k pour
lesquels nous cherchons une solution à SUBSET SUM. lesquels nous cherchons une solution à SUBSET SUM. Soit T la somme des éléments de S .Soit T la somme des éléments de S .
• Soit l’ensemble Z = S v { k+1 , T–k+1 } pour Soit l’ensemble Z = S v { k+1 , T–k+1 } pour lequel nous cherchons une solution à SET PARTITION.lequel nous cherchons une solution à SET PARTITION.
• Les deux problèmes sont équivalents.Les deux problèmes sont équivalents. La La transformationtransformation
est polynômiale et est polynômiale et déterministe.déterministe.
• Preuve ( => ) :Preuve ( => ) :
– Si A est un sous-ensemble de S de somme k , Si A est un sous-ensemble de S de somme k , alors son complément AC est de somme T–k .alors son complément AC est de somme T–k .
16 mars 2007 Cours de graphes 7 - Intranet 181
SUBSET SUM se réduit en SET PARTITIONSUBSET SUM se réduit en SET PARTITION--------------------------------------------------------------------------------------------------------------------------------------------------
--------• Soit l’ensemble d’entiers S et la constante k pour Soit l’ensemble d’entiers S et la constante k pour
lesquels nous cherchons une solution à SUBSET SUM. Soit T lesquels nous cherchons une solution à SUBSET SUM. Soit T la somme des éléments de S .la somme des éléments de S .
• Soit l’ensemble Z = S v { k+1 , T–k+1 } pour lequel Soit l’ensemble Z = S v { k+1 , T–k+1 } pour lequel nous cherchons une solution à SET PARTITION.nous cherchons une solution à SET PARTITION.
• Les deux problèmes sont équivalents.Les deux problèmes sont équivalents. La transformationLa transformation est polynômiale et déterministe.est polynômiale et déterministe.• Preuve ( => ) :Preuve ( => ) :
– Si A est un sous-ensemble de S de somme k , alors son Si A est un sous-ensemble de S de somme k , alors son complément AC est de somme T–k .complément AC est de somme T–k .
– Il suffit de choisir les ensembles B = A v { T–k+1 } et Il suffit de choisir les ensembles B = A v { T–k+1 } et BC = AC v { k+1 } pour avoir une solution à SET BC = AC v { k+1 } pour avoir une solution à SET PARTITION avec la somme identique T+1 .PARTITION avec la somme identique T+1 .
16 mars 2007 Cours de graphes 7 - Intranet 182
SUBSET SUM se réduit en SET PARTITIONSUBSET SUM se réduit en SET PARTITION--------------------------------------------------------------------------------------------------------------------------------------------------
--------• Soit l’ensemble d’entiers S et la constante k pour Soit l’ensemble d’entiers S et la constante k pour
lesquels nous cherchons une solution à SUBSET SUM. lesquels nous cherchons une solution à SUBSET SUM. Soit T la somme des éléments de S .Soit T la somme des éléments de S .
• Soit l’ensemble Z = S v { k+1 , T–k+1 } pour Soit l’ensemble Z = S v { k+1 , T–k+1 } pour lequel nous cherchons une solution à SET PARTITION.lequel nous cherchons une solution à SET PARTITION.
• Les deux problèmes sont équivalents.Les deux problèmes sont équivalents. La La transformationtransformation
est polynômiale et est polynômiale et déterministe.déterministe.
• Preuve ( <= ) :Preuve ( <= ) :
– Soient B et BC une partition de Z en solution de Soient B et BC une partition de Z en solution de SET PARTITION. k+1 et T–k+1 ne figurent pas dans SET PARTITION. k+1 et T–k+1 ne figurent pas dans le même sous-ensemble.le même sous-ensemble.
16 mars 2007 Cours de graphes 7 - Intranet 183
SUBSET SUM se réduit en SET PARTITIONSUBSET SUM se réduit en SET PARTITION--------------------------------------------------------------------------------------------------------------------------------------------------
--------• Soit l’ensemble d’entiers S et la constante k pour lesquels Soit l’ensemble d’entiers S et la constante k pour lesquels
nous cherchons une solution à SUBSET SUM. Soit T la somme nous cherchons une solution à SUBSET SUM. Soit T la somme des éléments de S .des éléments de S .
• Soit l’ensemble Z = S v { k+1 , T–k+1 } pour lequel nous Soit l’ensemble Z = S v { k+1 , T–k+1 } pour lequel nous cherchons une solution à SET PARTITION.cherchons une solution à SET PARTITION.
• Les deux problèmes sont équivalents.Les deux problèmes sont équivalents. La transformationLa transformation est polynômiale et déterministe.est polynômiale et déterministe.• Preuve ( <= ) :Preuve ( <= ) :
– Soient B et BC une partition de Z en solution de SET Soient B et BC une partition de Z en solution de SET PARTITION. k+1 et T–k+1 ne figurent pas dans le même PARTITION. k+1 et T–k+1 ne figurent pas dans le même sous-ensemble.sous-ensemble.
– Si T–k+1 est dans B , il suffit de choisir A égal à B \ Si T–k+1 est dans B , il suffit de choisir A égal à B \ { T–k+1 } pour que A soit un sous-ensemble de S de { T–k+1 } pour que A soit un sous-ensemble de S de somme k et donc une solution à SUBSET SUM.somme k et donc une solution à SUBSET SUM.
16 mars 2007 Cours de graphes 7 - Intranet 184
Un problème curieuxUn problème curieux----------------------------------------------------------------------------------------------------------------------------------
I S O M O R P H I S M E SI S O M O R P H I S M E S
D ED E
G R A P H E SG R A P H E S
16 mars 2007 Cours de graphes 7 - Intranet 185
Un problème curieuxUn problème curieux----------------------------------------------------------------------------------------------------------------------------------
• Deux graphes sont-ils identiques à Deux graphes sont-ils identiques à (re-)nommage des sommets près ?(re-)nommage des sommets près ?
16 mars 2007 Cours de graphes 7 - Intranet 186
Un problème curieuxUn problème curieux----------------------------------------------------------------------------------------------------------------------------------
• Deux graphes sont-ils identiques à Deux graphes sont-ils identiques à (re-)nommage des sommets près ?(re-)nommage des sommets près ?
AA
BB
CCDD
EEGG
HH
IIJJ
KK
16 mars 2007 Cours de graphes 7 - Intranet 187
Un problème curieuxUn problème curieux----------------------------------------------------------------------------------------------------------------------------------
• Deux graphes sont-ils identiques à Deux graphes sont-ils identiques à (re-)nommage des sommets près ?(re-)nommage des sommets près ?
AA
BB
CCDD
EEGG
HH
IIJJ
KK
11 22
3355
44
6677
881010
99
16 mars 2007 Cours de graphes 7 - Intranet 188
Un problème curieuxUn problème curieux----------------------------------------------------------------------------------------------------------------------------------
• Deux graphes sont-ils identiques à Deux graphes sont-ils identiques à (re-)nommage des sommets près ?(re-)nommage des sommets près ?
A1A1
B2B2
C3C3D4D4
E5E5GG
HH
IIJJ
KK
A1A1 B2B2
C3C3E5E5
D4D4
6677
881010
99
16 mars 2007 Cours de graphes 7 - Intranet 189
Un problème curieuxUn problème curieux----------------------------------------------------------------------------------------------------------------------------------
• Deux graphes sont-ils identiques à Deux graphes sont-ils identiques à (re-)nommage des sommets près ?(re-)nommage des sommets près ?
A1A1
B2B2
C3C3D4D4
E5E5G6G6
H7H7
I8I8J9J9
K10K10
A1A1 B2B2
C3C3E5E5
D4D4
G6G6H7H7
I8I8K10K10
J9J9
16 mars 2007 Cours de graphes 7 - Intranet 190
Un problème curieuxUn problème curieux----------------------------------------------------------------------------------------------------------------------------------
• Deux graphes sont-ils identiques à Deux graphes sont-ils identiques à (re-)nommage des sommets près ?(re-)nommage des sommets près ?
A1A1
B2B2
C3C3D4D4
E5E5G6G6
H7H7
I8I8J9J9
K10K10
A1A1 B2B2
C3C3E5E5
D4D4
G6G6H7H7
I8I8K10K10
J9J9
16 mars 2007 Cours de graphes 7 - Intranet 191
Un problème curieuxUn problème curieux----------------------------------------------------------------------------------------------------------------------------------
• GRAPH ISOMORPHISM est bien-sûr dans GRAPH ISOMORPHISM est bien-sûr dans NPNP ! !
16 mars 2007 Cours de graphes 7 - Intranet 192
Un problème curieuxUn problème curieux----------------------------------------------------------------------------------------------------------------------------------
• GRAPH ISOMORPHISM est bien-sûr dans GRAPH ISOMORPHISM est bien-sûr dans NPNP ! !
• On sait résoudre le problème dans On sait résoudre le problème dans PP pour de pour de nombreuses classes de graphes !nombreuses classes de graphes !
16 mars 2007 Cours de graphes 7 - Intranet 193
Un problème curieuxUn problème curieux----------------------------------------------------------------------------------------------------------------------------------
• GRAPH ISOMORPHISM est bien-sûr dans GRAPH ISOMORPHISM est bien-sûr dans NPNP ! !
• On sait résoudre le problème dans On sait résoudre le problème dans PP pour de pour de nombreuses classes de graphes !nombreuses classes de graphes !
• On ne connaît aucun algorithme dans On ne connaît aucun algorithme dans PP qui qui résolve toutes les instances !résolve toutes les instances !
16 mars 2007 Cours de graphes 7 - Intranet 194
Un problème curieuxUn problème curieux----------------------------------------------------------------------------------------------------------------------------------
• GRAPH ISOMORPHISM est bien-sûr dans GRAPH ISOMORPHISM est bien-sûr dans NPNP ! !
• On sait résoudre le problème dans On sait résoudre le problème dans PP pour de pour de nombreuses classes de graphes !nombreuses classes de graphes !
• On ne connaît aucun algorithme dans On ne connaît aucun algorithme dans PP qui qui résolve toutes les instances !résolve toutes les instances !
• On ne sait pas si GRAPH ISOMORPISM est dans On ne sait pas si GRAPH ISOMORPISM est dans PP ? ?
16 mars 2007 Cours de graphes 7 - Intranet 195
Un problème curieuxUn problème curieux----------------------------------------------------------------------------------------------------------------------------------
• GRAPH ISOMORPHISM est bien-sûr dans GRAPH ISOMORPHISM est bien-sûr dans NPNP ! !
• On sait résoudre le problème dans On sait résoudre le problème dans PP pour de pour de nombreuses classes de graphes !nombreuses classes de graphes !
• On ne connaît aucun algorithme dans On ne connaît aucun algorithme dans PP qui qui résolve toutes les instances !résolve toutes les instances !
• On ne sait pas si GRAPH ISOMORPISM est dans On ne sait pas si GRAPH ISOMORPISM est dans PP ? ?
• On ne sait toujours pas si GRAPH ISOMORPHISM est On ne sait toujours pas si GRAPH ISOMORPHISM est NN––PP–complet ! ! !–complet ! ! !
16 mars 2007 Cours de graphes 7 - Intranet 196
Un problème curieuxUn problème curieux----------------------------------------------------------------------------------------------------------------------------------
• GRAPH ISOMORPHISM est bien-sûr dans GRAPH ISOMORPHISM est bien-sûr dans NPNP ! !
• On sait résoudre le problème dans On sait résoudre le problème dans PP pour de pour de nombreuses classes de graphes !nombreuses classes de graphes !
• On ne connaît aucun algorithme dans On ne connaît aucun algorithme dans PP qui qui résolve toutes les instances !résolve toutes les instances !
• On ne sait pas si GRAPH ISOMORPISM est dans On ne sait pas si GRAPH ISOMORPISM est dans PP ? ?
• On ne sait toujours pas si GRAPH ISOMORPHISM est On ne sait toujours pas si GRAPH ISOMORPHISM est NN––PP–complet ! ! !–complet ! ! !
16 mars 2007 Cours de graphes 7 - Intranet 197
SynthèseSynthèse----------------------------------------------------------------------------------------------------------------------------------
• Problèmes NP-complets.Problèmes NP-complets.
• Réductions polynômiales.Réductions polynômiales.
16 mars 2007 Cours de graphes 7 - Intranet 198
m E r C i e Tm E r C i e Tb O n N e J o U r N é b O n N e J o U r N é
E ! ! !E ! ! !
N ‘ o U b L i E z P a S N ‘ o U b L i E z P a S d Ed E
p R é P a R e R v O sp R é P a R e R v O sT D ! ! !T D ! ! !