D´emonstration que le probl`eme HAMD
est NP-complet
Alexandre Blondin Mass´e
D´
epartement d’informatique
Universit´
e du Qu´
ebec `
a Montr´
eal
23 octobre 2014
Cours INF7440
D´epartement d’informatique
A. Blondin Mass´
e (UQAM)
23 octobre 2014
1 / 4
HAMD est NP-complet
Th´eor`eme
Le probl`eme HAMD est NP-complet.
I
Il est facile de voir que HAMD est de classe NP;
A. Blondin Mass´
e (UQAM)
23 octobre 2014
2 / 4
HAMD est NP-complet
Th´eor`eme
Le probl`eme HAMD est NP-complet.
I
Il est facile de voir que HAMD est de classe NP;
I
La r´
eduction est par contre plus complexe.
A. Blondin Mass´
e (UQAM)
23 octobre 2014
2 / 4
HAMD est NP-complet
Th´eor`eme
Le probl`eme HAMD est NP-complet.
I
Il est facile de voir que HAMD est de classe NP;
I
La r´
eduction est par contre plus complexe.
I
En g´en´eral, on montre que
k-VCD HAMD
A. Blondin Mass´
e (UQAM)
23 octobre 2014
2 / 4
R´eduction
A. Blondin Mass´
e (UQAM)
w
x
z
y
23 octobre 2014
3 / 4
R´eduction
Ww,z
A. Blondin Mass´
e (UQAM)
Ww,y
w
x
z
y
Ww,x
23 octobre 2014
Wx,y
3 / 4
R´eduction
Ww,z
A. Blondin Mass´
e (UQAM)
Ww,y
w
x
z
y
Ww,x
23 octobre 2014
Wx,y
3 / 4
R´eduction
Ww,z
Ww,y
w
x
z
y
Ww,x
s1
A. Blondin Mass´
e (UQAM)
Wx,y
s2
23 octobre 2014
3 / 4
R´eduction
Ww,z
Ww,y
w
x
z
y
Ww,x
s1
A. Blondin Mass´
e (UQAM)
Wx,y
s2
23 octobre 2014
3 / 4
R´eduction
Ww,z
Ww,y
w
x
z
y
Ww,x
s1
A. Blondin Mass´
e (UQAM)
Wx,y
s2
23 octobre 2014
3 / 4
R´eduction
Ww,z
Ww,y
w
x
z
y
Ww,x
s1
A. Blondin Mass´
e (UQAM)
Wx,y
s2
23 octobre 2014
3 / 4
R´eduction
Ww,z
Ww,y
w
x
z
y
Ww,x
s1
A. Blondin Mass´
e (UQAM)
Wx,y
s2
23 octobre 2014
3 / 4
R´eduction
Ww,z
Ww,y
w
x
z
y
Ww,x
s1
A. Blondin Mass´
e (UQAM)
Wx,y
s2
23 octobre 2014
3 / 4
R´eduction
Ww,z
Ww,y
w
x
z
y
Ww,x
s1
A. Blondin Mass´
e (UQAM)
Wx,y
s2
23 octobre 2014
3 / 4
R´eduction
Ww,z
Ww,y
w
x
z
y
Ww,x
s1
A. Blondin Mass´
e (UQAM)
Wx,y
s2
23 octobre 2014
3 / 4
R´eduction
Ww,z
Ww,y
w
x
z
y
Ww,x
s1
A. Blondin Mass´
e (UQAM)
Wx,y
s2
23 octobre 2014
3 / 4
R´eduction
Ww,z
Ww,y
w
x
z
y
Ww,x
s1
A. Blondin Mass´
e (UQAM)
Wx,y
s2
23 octobre 2014
3 / 4
R´eduction
Ww,z
Ww,y
w
x
z
y
Ww,x
s1
A. Blondin Mass´
e (UQAM)
Wx,y
s2
23 octobre 2014
3 / 4
R´eduction (suite)
I
On sait d´ej`a que HAMD est de classe NP;
A. Blondin Mass´
e (UQAM)
23 octobre 2014
4 / 4
R´eduction (suite)
I
On sait d´ej`a que HAMD est de classe NP;
I
On constate que la transformation est polynomiale;
A. Blondin Mass´
e (UQAM)
23 octobre 2014
4 / 4
R´eduction (suite)
I
On sait d´ej`a que HAMD est de classe NP;
I
On constate que la transformation est polynomiale;
I
Pour chaque couverture des arˆ
etes, on peut construire
un cycle hamiltonien;
A. Blondin Mass´
e (UQAM)
23 octobre 2014
4 / 4
R´eduction (suite)
I
On sait d´ej`a que HAMD est de classe NP;
I
On constate que la transformation est polynomiale;
I
Pour chaque couverture des arˆ
etes, on peut construire
un cycle hamiltonien;
I
` chaque cycle hamiltonien, on peut lui associer une
A
couverture des arˆ
etes par les sommets.
A. Blondin Mass´
e (UQAM)
23 octobre 2014
4 / 4