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.

Contents:

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

Bibliography

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

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