Résolution exacte de problèmes NP-difficiles

ECTS : 3

Description du contenu de l'enseignement :

Objectifs : Enseigner les techniques de la résolution exacte des problèmes NP-difficiles par des algorithmes à complexité non-triviale (dits algorithmes modérément exponentiels) et par des algorithmes paramétrés. Pour chacune de ces techniques, des exemples de problèmes sur lesquels elles sont appliquées seront présentés et discutés.

Complexité au pire des cas
Techniques de résolution exacte (Programmation dynamique, Arbres de recherche, Enumération, Inclusion – exclusion, Recherche locale)
Application à la résolution exacte de problèmes NP-difficiles (Coloration, Voyageur de commerce, Stable, Coupe maximum, Stable maximum, Couverture d'ensembles)
Techniques de l’algorithmique paramétrée (Kernelisation, Arbres de recherche, …)
Application à la résolution paramétrée de problèmes NP-difficiles (Couverture de sommets minimum, Feedback vertex set, k-Couverture de sommets)
 

Compétence à acquérir :

• Algorithms design technique for parameterized and exact algorithms.
• Technique to prove strong hardness for NP-hard problems.

Bibliographie, lectures recommandées :

Bibliographie

• M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015.
• F. V. Fomin, D. Kratsch, Exact Exponential Algorithms, Springer-Verlag, 2010.