Graphs

This lecture presents different ways to efficiciently address « difficult » (NP-hard) problems.

Description

We focus on two approaches:

• approximation algorithms where the optimality of the desired solutions is relaxed;
• and parameterized (FPT) algorithms where exact solutions are expected but whose « combinatorial complexity » depends on some parameter (not necessarily the size of the instance).

In other words, parameterized algorithms computes exact solutions (for NP-hard problems in general instances) in polynomial time in specific classes of instances. Parameterized complexity is one of the current hot topic in theoretical computer science. Considered problems to illustrate these methods are classical optimization problems such as Load Balancing problems and graph problems such as Traveling Salesman Problem, Vertex Cover, Independent Set…

Grading

• Midterm Exam or Scientific presentation depending on the number of students (1/3).
• Final Exam (2/3)

Resources

• Mainly chapters 8 et 9
• Approximation Algorithms, Vazirani.
• Parameterized Complexity, Cygan et al.
• Exact Exponential Algorithms, Fomin and Kratsch.
• M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, S. Saurabh: Parameterized Algorithms. Springer 2015, ISBN 978-3-319-21274-6, pp. 3-555.