Une famille de problèmes
NP-complets sur les graphes.
L'identification de problèmes NP-complets peut souvent sembler
laborieuse, classant pas à pas de nouveaux problèmes,
avec la nécessité de réécrire de nouvelles
réductions même si elles sont courtes et parfois pour
d'infimes variations de problèmes déjà
classés comme NP-complets. Une manière de classer
plusieurs problèmes d'un coup est d'identifier un
problème qui soit à leur intersection et de prouver qu'il
est
NP-complet (entrainant par là que les autres qui le
généralisent sont aussi NP-complets), ou bien
d'identifier un principe de réduction qui permet de
définir une classe de problèmes avec sa classe de
réductions.
Il existe de tels théorèmes de NP-complétude
classant des familles de problèmes de graphes. L'objectif du
sujet est de lire et expliquer un article de Yannakakis sur ce sujet :
D'autres
références (pas
exhaustif).
- Computer and Intractability: a
guide to the theory of NP-completeness, livre de R. Garey et D.
Johnson, Freeman (1979). Pour
la culture.
- Introduction to Graph Theory,
livre de D. West, Prentice Hall
(2001). Pour des éclaircissement sur les graphes si
nécessaire, et sur des théorèmes de Ramsey.
Retour à la page des sujets.