Ects : 3

Enseignant responsable :

• EUN JUNG KIM
• MICHAIL LAMPIS

Volume horaire : 15

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)

Pré-requis recommandés :

Familiarity with graph theory and data structure will be useful

Pré-requis obligatoires :

Undergraduate level acquaintance with algorithms, running time analysis, computational complexity

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.