Résumé | Some important part of the research on design and analysis of algorithms is trying to find better approaches for solving NP-hard problems. In most cases the notion of "solving a problem exactly" is relaxed: approximation algorithms, heuristics, randomized algorithms, parameterized algorithms, algorithms for restricted inputs, etc.
Another approach, called moderately exponential-time algorithms, has attracted a lot of interest recently. Such an algorithm indeed tries to cope with NP-hardness in the strongest sense: the problem needs to be solved by the algorithm for all inputs and worst-case running time is considered. Techniques for the design and analysis of moderately exponential-time algorithms will be presented, among them branching algorithms, dynamic programming algorithms and inclusion exclusion algorithms.
The breakthrough result of Bjorklund, Husfeldt and Koivisto (FOCS 2006), a O*(2^n) algorithm to compute the chromatic number of an n-vertex graph will be outlined. |