Cours de graphes

16 mars 2007

Cours de graphesProblèmes NP-complets.

Réductions polynômiales.

16 mars 2007

Les grandes lignes du cours• Définitions de base• Connexité• Les plus courts chemins• Dijkstra et Bellmann-Ford• Arbres• Arbres de recouvrement minimaux • Problèmes de flots• Coloriage de graphes, graphes

planaires• Couplage• Chemins d’Euler et de Hamilton• Problèmes NP-complets

16 mars 2007

Rappels sur la NP-complétude-----------------------------------------------------------------

R A P P E L S

S U R L A

N P – C O M P L E T U D E

16 mars 2007


• La question :

• Y aurait-il par hasard des problèmes dont la complexité intrinsèque est exponentielle ?

• Pour un tel problème, tout algorithme pour le résoudre serait exponentiel en temps !

• La réponse :

• Probablement OUI !

• Malheureusement ! ! !

• On ne sait rien de définitif ! ! !

P = N Pou bien

P = N P

/

16 mars 2007


• La classe de problèmes « P » !

• Ce sont les problèmes qui acceptent un algorithme :

– polynômial,

– déterministe,

– qui résout toutes les instances.

La complexité est un polynômeen termes de la taille du problème.

Il n’y a aucun élément de chance oud’indication venant de l’extérieur.

Aucune instancen’est trop difficile.

16 mars 2007


• La classe de problèmes « N P » !

• Ce sont les problèmes qui acceptent un algorithme :

– polynômial,

– non-déterministe,

– qui résout toutes les instances.

Il peut y a avoir des élémentsde chance ou des

indications venant de l’extérieur.

16 mars 2007


• Nous remplaçons une exploration à l’aide du back-track

– par un appel à l’oracle.

• L’oracle répond au bout de . . . ?

– La complexité de l’oracle est bien-sûr en O ( 1 ) .

• Je sais réaliser un oracle en temps exponentiel !

– Il suffit de faire un back-track en cachette ! ! !

16 mars 2007


• Autre formulation de la classe de problèmes « N P » !

• Ce sont les problèmes qui :

– acceptent, pour chaque instance, un nombre borné de candidats à être la solution,

– pour lesquels, la vérification qu’un candidat quelconque est solution appartient à « P ».

16 mars 2007


• Théorème : P N PU

N P

P

P = N P c’est-à-dire N P \ P = o/? ?

? ? ? ? ?

16 mars 2007


• Définissons la classe « N P C », c’est-à-dire les problèmes « N-P-complets » :

N P

P

N P C

Ce seront les problèmes les plus difficiles de « N P » !

L’idée : Si eux sont dans « P », alors « P = N P » ! ! !

Facile.

Difficile.

16 mars 2007


• Il nous faut une notion de traduction !

– Soit un problème P : D -> BOOL

– Soit un problème P : D -> BOOL

• P se réduit polynômialement en P , noté P <= P

si et seulement si :

– il existe f : D -> D avec f e P– telle que pour tout x e D : P ( x ) = P ( f ( x ) )

11

22

1 12 2

1 2

1

1 2

P

16 mars 2007


• L’idée derrière la traduction :

P1x Vrai ou Faux

Calcul !

P2f ( x )

Traduction !

Vrai ou FauxCalcul !

Le mêmerésultat !

16 mars 2007


• Définition :

• La classe « N P C » est la classe des problèmes P tels que :

– P e N P .

– Pour tout Q e N P on a : Q <= P .

• Tout le monde se réduit vers P .

• P est donc le plus difficile ! ! !

• Si P , P’ e N P C , alors il sont ex aequo en difficulté :

P <= P’ et P’ <= P .P P

P

16 mars 2007


• Et si « N P C » était vide ? ? ?– C’est-à-dire, un tel problème universel n’existe pas ! !

!

• Théorème (Cook, 1971) :

– SAT e N P C .

• Il n’y a pas plus difficile (dans N P C) que la logique.

• Principe de la preuve :– Tout problème dans « N P » peut être traduit en une

formule logique.– Analogie : Tout texte peut être traduit en une formule

alphabétique.

16 mars 2007


N P

P

N P CSAT

16 mars 2007

• Conséquences :

• S’il existe un seul problème P e N P C – pour lequel on trouve un algorithme en temps

polynômial et déterministe,

– alors P = N P !

• S’il existe un seul problème P e N P C – pour lequel on prouve qu’un algorithme en

temps polynômial et déterministe ne peut pas exister,

– alors P = N P !


/

16 mars 2007


• Concrètement :

• Vous avez un problème qui vous résiste ? • Essayez de savoir s’il est N-P-complet !

– le Garey and Johnson, ou Internet, ou . . .

• Comment prouver qu’il est N-P-complet ? ? ?

– Prouvez que votre problème P est dans N P et– prenez un problème A de N P C et montrez que A <= P

P

On vous donnela solution etvous vérifiezque c’en est

bien une !

16 mars 2007

Réductions polynômiales-----------------------------------------------------------------

Q U E L Q U E S

R E D U C T I O N S

P O L Y N O M I A L E S

16 mars 2007


• Nous construirons les réductions polynômiales suivantes :

£ PSAT

£P

CIRCUIT-SAT

£P3-SAT FNC

SUBSET SUM

CLIQUE VERTEX COVER£P

et VERTEX C.£P£ P

£P SET PARTITION

0-1 LINEAR PROG.

16 mars 2007



£ PSAT

£P

CIRCUIT-SAT

£P3-SAT FNC

SUBSET SUM


et VERTEX C.£P£ P

£P SET PARTITION

0-1 LINEAR PROG.

16 mars 2007



£ PSAT

£P

CIRCUIT-SAT

£P3-SAT FNC

SUBSET SUM


et VERTEX C.£P£ P

£P SET PARTITION

0-1 LINEAR PROG.

16 mars 2007



£ PSAT

£P

CIRCUIT-SAT

£P3-SAT FNC

SUBSET SUM


et VERTEX C.£P£ P

£P SET PARTITION

0-1 LINEAR PROG.

16 mars 2007



£ PSAT

£P

CIRCUIT-SAT

£P3-SAT FNC

SUBSET SUM


et VERTEX C.£P£ P

£P SET PARTITION

0-1 LINEAR PROG.

16 mars 2007

SAT se réduit en CIRCUIT-SAT-----------------------------------------------------------------

• CIRCUIT-SAT– « n » variables logiques et un circuit logique

construit à partir des circuits de base et , ou ou not .

– La question : Le circuit peut-il rendre la valeur « Vrai » pour un choix adéquat des valeurs des variables ?

CIRCUIT-SAT est bien dans NP , car si on nousdonne une solution nous sommes capables de

vérifier que c’en est bien une en tempspolynômial et de façon déterministe !

16 mars 2007


• CIRCUIT-SAT– « n » variables logiques et un circuit logique

construit à partir des circuits de base et , ou ou not .

– La question : Le circuit peut-il rendre la valeur « Vrai » pour un choix adéquat des valeurs des variables ?

• La réduction :

– Nous allons traduire une formule logique de SAT en un circuit de CIRCUIT-SAT qui donne les mêmes résultats !

16 mars 2007


• La réduction :– Variable 3-SAT -> variable CIRCUIT-SAT.

– ù x -> x

– ( a v b v . . . v z ) -> a b . . . . . . z

– ( a b . . . z ) -> a b . . . . . . z

vv v

. . .La réductionest dans P !

. . .

16 mars 2007



£ PSAT

£P

CIRCUIT-SAT

£P3-SAT FNC

SUBSET SUM


et VERTEX C.£P£ P

£P SET PARTITION

0-1 LINEAR PROG.

16 mars 2007

SAT se réduit en 3-SAT FNC-----------------------------------------------------------------

• Une formule SAT est une formule de profondeur quelconque qui comporte des littéraux ou leurs négations ainsi que des conjonctions et des disjonctions binaires.

( ( x v ù y ) v ( ( y ( z v t ) ) ù x ) )

• Une formule 3-SAT FNC (forme normale conjonctive) est une formule qui comporte une conjonction n-aire composée de disjonctions avec trois littéraux ou leurs négations.

( a v ù b v c ) ( a v d v e ) . . . ( ù d v c v e )

v v

v v v

3-SAT FNC est bien dans NP , car si on nous donne unesolution nous sommes capables de vérifier que c’en est

bien une en temps polynômial et de façon déterministe !

16 mars 2007


• Une formule SAT est une formule de profondeur quelconque qui comporte des littéraux ou leurs négations ainsi que des conjonctions et des disjonctions binaires.

( ( x v ù y ) v ( ( y ( z v t ) ) ù x ) )

• Une formule 3-SAT FNC (forme normale conjonctive) est une formule qui comporte une conjonction n-aire composée de disjonctions avec trois littéraux ou leurs négations.

( a v ù b v c ) ( a v d v e ) . . . ( ù d v c v e )

• Nous allons « aplatir » notre formule SAT en une formule 3-SAT FNC.

v

v v

v v

16 mars 2007


• A une variable SAT nous associons une variable 3-SAT FNC.

• A une formule SAT de la forme ( A op B ) nous associons une nouvelle variable y pour laquelle nous affirmons que

– y est vraieet– y est équivalente à ( A op B )

• Ensuite, il suffit de traduire cette équivalence en une disjonction.

vy ( y <=> A op B )

16 mars 2007


• Une formule de la forme ( y <=> A op B ) correspond à une table de vérité avec 8 lignes. Nous en sélectionnons les 4 lignes qui sont fausses et nous les traduisons en une formule f qui est une disjonction de conjonctions :

( y A B ) v ( ù y ù A B ) v ( y ù A ù B ) v . . .

• La négation de f est la formule recherchée. D’après de « De Morgan », nous obtenons :

( ù y v ù A v ù B ) ( y v A v ù B ) ( ù y v A v B ) . . .

v

v v v v v v

v v

16 mars 2007


• 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 sont fausses et nous les traduisons en une formule f qui est une disjonction de conjonctions :

( y A B ) v ( ù y ù A B ) v ( y ù A ù B )

• La négation de f est la formule recherchée. D’après de « De Morgan », nous obtenons :

( ù y v ù A v ù B ) ( y v A v ù B ) ( ù y v A v B )

• La même approche reste vraie pour tous les opérateurs binaires, comme et , ou , => , <=> , . . .

v

v v v v v v

v

16 mars 2007


U N

E X E M P L E

16 mars 2007


( ( ( x => x ) x ) v x )v

2 3 2 1

v

x 1

v

x 2=>

x 3x 2

y 1

y 2

y 3

y 1

v( y <=> ( y v x ) )1v

v

( y <=> ( y x ) )2

( y <=> ( x => x ) )3 2 3

2 1

3 2

v

16 mars 2007


( ( ( x => x ) x ) v x )v

2 3 2 1

y 1

v( y <=> ( y v x ) )1v

v

( y <=> ( y x ) )2

( y <=> ( x => x ) )3 2 3

2 1

3 2

v

y 3 x 2 x 3 . . .

0 0 0 00 0 1 00 1 0 1

0 1 1 01 0 0 1

1 0 1 11 1 0 01 1 1 1

f = ( ù y ù x ù x )

v ( ù y ù x x ) v . . .

v

3 2

v

3

v

3 2

v

3

16 mars 2007


( ( ( x => x ) x ) v x )v

2 3 2 1

y 1

v( y <=> ( y v x ) )1v

v

( y <=> ( y x ) )2

( y <=> ( x => x ) )3 2 3

2 1

3 2

v

y 3 x 2 x 3 . . .

0 0 0 00 0 1 00 1 0 1

0 1 1 01 0 0 1

1 0 1 11 1 0 01 1 1 1

ù f = ( y v x v x )

( y v x v ù x ) . . .

v

3 2 3

v

3 2 3

16 mars 2007


( ( ( x => x ) x ) v x )v

2 3 2 1

y 1

v( y <=> ( y v x ) )1v

v

( y <=> ( y x ) )2

2 1

3 2

v

y 3 x 2 x 3 . . .

0 0 0 00 0 1 00 1 0 1

0 1 1 01 0 0 1

1 0 1 11 1 0 01 1 1 1

( y v x v x )3 2 3

v( y v x v ù x )3 2 3

v. . .

16 mars 2007



£ PSAT

£P

CIRCUIT-SAT

£P3-SAT FNC

SUBSET SUM


et VERTEX C.£P£ P

£P SET PARTITION

0-1 LINEAR PROG.

16 mars 2007

3-SAT FNC se réduit en CLIQUE-----------------------------------------------------------------

• Une clique d’un graphe G = ( V , E ) est un sous-ensemble des sommets qui sont tous voisins les uns des autres !

Une clique de3 sommets !

16 mars 2007


• Une clique d’un graphe G = ( V , E ) est un sous-ensemble des sommets qui sont tous voisins les uns des autres !

• Question : Y a-t-il G une clique de k sommets ?

• CLIQUE est dans NP car nous savons vérifier dans P si un ensemble de sommets est une clique ou non !

L’unique cliquede 4 sommets !

16 mars 2007


F = C . . . Cv

1

C = T v T v T i i,1 T = x | ù xpi,j p

k

v

i,2 i,3

• Soit une formule 3-SAT FNC constituée de k conjonctions :

• Nous allons montrer que cette formule peut être rendue vraie si et seulement s’il existe une clique de taille k dans un certain graphe.

• CLIQUE sera donc au moins aussi difficile que 3-SAT FNC, c’est-à-dire vraisemblablement exponentiel en général.

16 mars 2007


• La construction du graphe :

• A chaque terme T nous associons un sommet.

• Les sommets T et T sont voisins dans le graphe ssi :

– i et m sont différents,– les termes ne sont pas la négation l’un de l’autre.

i,j

i,j m,n

16 mars 2007


• La construction du graphe :

• A chaque terme T nous associons un sommet.

• Les sommets T et T sont voisins dans le graphe ssi :

– i et m sont différents,– les termes ne sont pas la négation l’un de l’autre.

• Cette construction est clairement déterministe et peut se faire en temps polynômial.

i,j

i,j m,n

16 mars 2007


( x v ù x v ù x )1 2 3 ( ù x v x v x )1 2 3

v ( x v x v x )1 2 4

v

x1 ù x 2 ù x 3

ù x1

x 2

x 3

x1

x 2

x 4

En construction . . . NONCOMPATIBLES !

16 mars 2007


( x v ù x v ù x )1 2 3 ( ù x v x v x )1 2 3

v ( x v x v x )1 2 4

v

x1 ù x 2 ù x 3

ù x1

x 2

x 3

x1

x 2

x 4

Le voilà !

16 mars 2007


( x v ù x v ù x )1 2 3 ( ù x v x v x )1 2 3

v ( x v x v x )1 2 4

v

• Clairement, notre formule peut être rendu vraie seulement si nous trouvons dans chaque terme de la conjonction au moins une fois la valeur vrai.

• De plus, ces choix doivent être compatibles !

• Autrement dit, ils doivent correspondre à une clique que nous pouvons former dans le graphe !

• Rendre vraie la formule ou trouver une clique dans le graphe sont donc des problèmes de même difficulté ! ! !

16 mars 2007


( x v ù x v ù x )1 2 3 ( ù x v x v x )1 2 3

v ( x v x v x )1 2 4

v

x1 ù x 2 ù x 3

ù x1

x 2

x 3

x1

x 2

x 4

Une solution !

16 mars 2007


( x v ù x v ù x )1 2 3 ( ù x v x v x )1 2 3

v ( x v x v x )1 2 4

v

x1 ù x 2 ù x 3

ù x1

x 2

x 3

x1

x 2

x 4

Une autre solution !

16 mars 2007



£ PSAT

£P

CIRCUIT-SAT

£P3-SAT FNC

SUBSET SUM


et VERTEX C.£P£ P

£P SET PARTITION

0-1 LINEAR PROG.

16 mars 2007

CLIQUE se réduit en VERTEX COVER-----------------------------------------------------------------

• Nous nous donnons un graphe G = ( V , E ) avec n sommets et une constante naturelle k .

• Question : Pouvons-nous trouver un sous-ensemble V’ d’au plus k sommets de façon à ce que toute arête ait au moins une extrémité dans V’ ?

k = 2

OUI ! ! !

Les arêtes sont dansl’ensemble ou elles

traversent la frontière !

Nous sommescapablesde vérifierune solution entemps polynômialet déterministe ! ! !

16 mars 2007


• Pourquoi est-ce un VERTEX COVER ?• C’en est un parce que les sommets en dehors de

V’ n’ont aucune arête en commun ! ! !• Autrement dit, les arêtes absentes comportent

une clique de taille | V | – | V’ | , c’est-à-dire n – k .

Considérons legraphe G’ qui

contient les arêtesabsentes de G !

G’ possède alorsune clique detaille n – k .

16 mars 2007


• Pour un graphe avec n sommets, il est équivalent de – de trouver un VERTEX COVER de taille k ou– de trouver une CLIQUE de taille n – k dans le

graphe complémentaire.

Considérons legraphe G’ qui

contient les arêtesabsentes de G !

G’ possède alorsune clique detaille n – k .

La transformation estdéterministe etpolynômiale.

16 mars 2007



£ PSAT

£P

CIRCUIT-SAT

£P3-SAT FNC

SUBSET SUM


et VERTEX C.£P£ P

£P SET PARTITION

0-1 LINEAR PROG.

16 mars 2007

VERTEX COVER se réduit en SUBSET SUM-------------------------------------------------------------------------

--• Nous avons :

– un ensemble S d’entiers naturels non nuls,– une constante k .

• La question est la suivante :

– Pouvons-nous trouver un sous-ensemble de S dont la somme vaut k ?

S = { 13 , 17 , 23 , 41 , 65 , 69 } et k = 105

OUI ! ! !Une autre solution ! ! !

16 mars 2007


--• Nous avons :

– un ensemble S d’entiers naturels non nuls,– une constante k .

• La question est la suivante :

– Pouvons-nous trouver un sous-ensemble de S dont la somme vaut k ?

• Le problème est dans NP , car la vérification est polynômiale et déterministe !

16 mars 2007


--• Nous considérons une matrice d’adjacence :

4

3

5a

b

cd

e

f

a b c d e f

12345

11000 Il y a deux occurrences

de 1 sur chaque colonne !

12

L’arête b est incidenteaux sommets 1 et 2 !

16 mars 2007


--• Nous considérons une matrice d’adjacence :

4

12 3

5a

b

cd

e

f

a b c d e f

12345

11000

10010

10001

00011

01100

00101

16 mars 2007


--• Nous rajoutons une matrice identité !• Nous rajoutons une colonne au début !• A lire en base 4, il n’y a pas de retenue !• Et les nombres sont tous différents !• Chaque ligne de la matrice donne un nombre de S !

a b c d e f

12345

11000

10001

00011

01100

00101

0 0 0 0 10 0 0 1 00 0 1 0 00 1 0 0 01 0 0 0 00 0 0 0 0

10010000001

11111000000

3 3 3 3 33| V |

+= 1= 4= 16= . . .

= x= y

16 mars 2007


--Le graphe contient un VERTEX COVER de taille ksi nous pouvons choisir de telles lignes afinque chaque colonne comporte2 occurrences de 1 !

4

12 3

5a

b

cd

e

f

a b c d e f

12345

11000

10010

10001

00011

01100

00101

V

{ 1 , 2 , 5 } est un VERTEXCOVER de 3 sommets ! ! !

16 mars 2007Soit k = k


--• Nous rajoutons une matrice identité !• Nous rajoutons une colonne au début !• A lire en base 4, il n’y a pas de retenue !• Et les nombres sont tous différents !• Chaque ligne de la matrice donne un nombre de S !

a b c d e f

12345

11000

10001

00011

01100

00101

0 0 0 0 10 0 0 1 00 0 1 0 00 1 0 0 01 0 0 0 00 0 0 0 0

10010000001

11111000000

2 2 2 2 22

+= 1= 4= 16= . . .

= x= y

S V

16 mars 2007


--• Nous avons un VERTEX COVER de taille k ssi nous avons un SUBSET SUM de valeur k .

• Soit le VERTEX COVER.

• Chaque colonne comporte au moins une fois le 1 ! ! ! Nous choisissons d’autres lignes pour compléter à 2 !

V

S

11000

10001

00011

01100

00101

0 0 0 0 10 0 0 1 00 0 1 0 00 1 0 0 01 0 0 0 00 0 0 0 0

10010000001

11111000000

Nous avons une somme de k = k V 2 2 2 2 22S

16 mars 2007


--• Nous avons un VERTEX COVER de taille k ssi nous avons un SUBSET SUM de valeur k .

• Soit le SUBSET SUM.

• Nous en extrayons un VERTEX COVER !

V

S

11000

10001

00011

01100

00101

0 0 0 0 10 0 0 1 00 0 1 0 00 1 0 0 01 0 0 0 00 0 0 0 0

10010000001

11111000000

16 mars 2007


--

U N

E X E M P L E

N U M E R I Q U E

16 mars 2007


--11000

10001

00011

01100

00101

0 0 0 0 10 0 0 1 00 0 1 0 00 1 0 0 01 0 0 0 00 0 0 0 0

10010000001

11111000000

1 =4 =

16 =64 =

256 =1024 =

5440 =4356 =4101 =5136 =4177 =

Le VERTEX COVER{ 1 , 2 , 5 } donne :

544043564177

14

161024

15018

k = 15018 = 3 S 2 2 2 2 22

16 mars 2007


--11000

10001

00011

01100

00101

0 0 0 0 10 0 0 1 00 0 1 0 00 1 0 0 01 0 0 0 00 0 0 0 0

10010000001

11111000000

1 =4 =

16 =64 =

256 =1024 =

5440 =4356 =4101 =5136 =4177 =

Le VERTEX COVER{ 2 , 4 , 5 } donne :

435651364177

14

64256

102415018

k = 15018 = 3 S 2 2 2 2 22

16 mars 2007



£ PSAT

£P

CIRCUIT-SAT

£P3-SAT FNC

SUBSET SUM


et VERTEX C.£P£ P

£P SET PARTITION

0-1 LINEAR PROG.

16 mars 2007

SUBSET SUM se réduit en 0-1 LINEAR PROG.-------------------------------------------------------------------------

-------• Nous avons un n-uplet X de variables qui

prennent 0 ou 1 comme valeurs.

• Nous avons p inéquations d’inconnue X :

• La question : Pouvons-nous trouver un vecteur X qui satisfait toutes les inéquations ?

• Le problème est bien dans NP !

a x + . . . + a x <= b1,1 1 1,n n 1

a x + . . . + a x <= bp,1 1 p,n n p

. . .Sous formematricielle :

A X <= B

16 mars 2007

SUBSET SUM se réduit en 0-1 LINEAR PROG.-------------------------------------------------------------------------

-------• Soit l’ensemble S = { s , . . . , s } de

nombres et la constante k .

• Nous construisons les deux inégalités :

• La transformation est dans P .• Trivial : k peut être obtenue comme somme de

nombres de S , si et seulement si, le système de programmation 0–1 admet une solution.

s x + . . . + s x <= k1 1 n n Celles-ciéquivalent àune égalité !

1 n

– s x – . . . – s x <= – k1 1 n n

==

16 mars 2007



£ PSAT

£P

CIRCUIT-SAT

£P3-SAT FNC

SUBSET SUM


et VERTEX C.£P£ P

£P SET PARTITION

0-1 LINEAR PROG.

16 mars 2007

SUBSET SUM se réduit en SET PARTITION-------------------------------------------------------------------------

----

S = { 17 , 37 , 48 , 70 , 76 }

OUI ! ! !

• Le problème SET PARTITION consiste à savoir si un ensemble S de nombres naturels peut être décomposé en deux sous-ensembles de nombres de sommes égales.

• Le problème est bien dans NP !

16 mars 2007


----• Soit l’ensemble d’entiers S et la constante k

pour lesquels nous cherchons une solution à SUBSET SUM. Soit T la somme des éléments de S .

• Soit l’ensemble Z = S v { k+1 , T–k+1 } pour lequel nous cherchons une solution à SET PARTITION.

• Les deux problèmes sont équivalents. La transformation

est polynômiale et déterministe.

• Preuve ( => ) :– Si A est un sous-ensemble de S de somme k ,

alors son complément AC est de somme T–k .– Il suffit de choisir les ensembles B = A v { T–

k+1 } et BC = AC v { k+1 } pour avoir une solution à SET PARTITION avec la somme identique T+1 .

16 mars 2007


----• Soit l’ensemble d’entiers S et la constante k

pour lesquels nous cherchons une solution à SUBSET SUM. Soit T la somme des éléments de S .

• Soit l’ensemble Z = S v { k+1 , T–k+1 } pour lequel nous cherchons une solution à SET PARTITION.

• Les deux problèmes sont équivalents. La transformation

est polynômiale et déterministe.

• Preuve ( <= ) :– 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 sous-ensemble.

– 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 somme k et donc une solution à SUBSET SUM.

16 mars 2007

Un problème curieux-----------------------------------------------------------------

I S O M O R P H I S M E S

D E

G R A P H E S

16 mars 2007

Un problème curieux-----------------------------------------------------------------• Deux graphes sont-ils identiques à

(re-)nommage des sommets près ? A1

B2

C3D4

E5G6

H7

I8J9

K10

A1 B2

C3E5

D4

G6H7

I8K10

J9

16 mars 2007

Un problème curieux-----------------------------------------------------------------

• GRAPH ISOMORPHISM est bien-sûr dans NP !

• On sait résoudre le problème dans P pour de nombreuses classes de graphes !

• On ne connaît aucun algorithme dans P qui résolve toutes les instances !

• On ne sait pas si GRAPH ISOMORPISM est dans P ?

• On ne sait toujours pas si GRAPH ISOMORPHISM est N–P–complet ! ! !

16 mars 2007

Synthèse-----------------------------------------------------------------

• Problèmes NP-complets.

• Réductions polynômiales.

Documents

Cours de graphes