Résolution exacte de problèmes NP-complets et difficiles

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.

Contenu :

• Techniques de résolution exacte (Programmation dynamique, Arbres de recherche, Enumération, Inclusion – exclusion, Recherche locale) et outils pour analyse de leur complexité

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

Bibliography

• R. G. Downey, M. R. Fellows, Parameterized Complexity, Springer-Verlag, 1999.

• F. V. Fomin, D. Kratsch, Exact Exponential Algorithms, Springer-Verlag, 2010.