Exact algorithms for NP-complete and hard problems

Objective: The course presents the main techniques and tools for the design and analysis of exact algorithms for NP-complete/hard problems, as well as examples of applications of such algorithms and techniques.


  • Exact solution methods (Dynamic programming, Search trees, Enumeration, Inclusion – exclusion, Local search) and tools for their complexity evaluation

  • Applications (Coloring, TSP, Independent Set, Cut, Set Covering)

  • Techniques for the design of parameterized algorithms (Kernelization, Search trees, Random separation, Color coding, etc.)

  • Applications (Vertex cover, Feedback vertex set, k-Covering, etc.)


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

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