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).

Retour à la page des sujets.