Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

Parameterized Algorithms (SS 2014)

Course Description

It is a (sad) empirical fact that most computational problems that are motivated by real-life problems are (at least!) NP-hard. So they cannot—using current algorithmic technology—be solved exactly within "reasonable" time bounds. How do we cope with this pervasive (and seemingly inescapable) hardness?

In this course, we introduce you to a very successful approach for solving hard problems fast: parameterized algorithms. The primary motivation for this approach is the observation that the computational hardness of many hard problems can be "isolated" to one or more aspects or parameters of the problem. During the course, we will explore algorithmic and structural techniques that can take advantage of this observation. In particular, we will discuss:

  1. Parameterized Algorithms: algorithms whose running times are exponential only in the chosen parameter, and are polynomial in the instance size. If the parameter is "small" in real-life inputs, then this leads to fast exact algorithms that work well in practice.
  2. Kernelization Algorithms: algorithms that reduce the size of the problem to a (hopefully small) function of the parameter. This provides a theoretical framework to understand the power of preprocessing heuristics.
  3. Hardness: How can we prove that certain problems do not have a parameterized or kernelization algorithm for a particular parameter?

Parameterized Algorithms is a very lively field of current research.

Basic Information

Lectures Tuesdays 10:00-12:00
Tutorials Thursdays 16:00-18:00
Location E1.4 Room 021
Lecturers Erik Jan van Leeuwen and G Philip
Course Language English
Course Mailing List For announcements and discussion. If you want to follow the course, you should join this list. If you want to credit the course, you should join the mailing list on or before April 30, 2014.
Prerequisites The course assumes that you are familiar with algorithms, complexity, and graphs.
At Saarland University, these fundamentals are taught mostly in the course Grundzüge von Algorithmen und Datenstrukturen (Algorithms and Data Structures) and some also in the course Grundzüge der Theoretischen Informatik.
Literature You do not need to buy a book for this course. Instead, you are expected to make notes during the lectures. However, the content of this course is based on four recent books on parameterized algorithms, that you can find in the library.
Credits 6 credits, graded
Examination The course has two exams: one mid-semester test and one final exam. The mid-semester test accounts for 25% of your final grade, the final exam for the remaining 75%. You can only take part in the final exam if you have done the mid-semester test.
Re-exam There will be a possibility for a re-exam of the final exam. You can only take part in the re-exam if you have done the mid-semester test.
Exam Dates Mid-term: Friday, June 13, 14.00 - 17.00, E1.4 Room 021.
Final exam: Friday, August 1, 9.00 - 12.00, E1.4 Room 023.
Re-exam: Tuesday, September 16, 14.00 - 17.00, E1.4 Room 021.

Schedule

Topics on future dates are tentative.

DateTopicExercises
15 AprIntro & Branching
22 AprIterative Compression
29 AprColor Coding INo tutorial on May 1 (Labor Day)
6 MayColor Coding II
13 MayImportant Separators I
20 MayImportant Separators II
27 MayTreewidth INo tutorial on May 29 (Ascension)
3 JunTreewidth II
10 JunTreewidth III
17 JunKernelization Algorithms INo tutorial on June 19 (Corpus Christi)
24 JunKernelization Algorithms II
1 JulKernelization Algorithms III
8 JulW-hardness
15 JulKernel Lower Bounds
22 JulETH Hardness


More Courses of the Algorithms and Complexity Group

Search MPII (type ? for help)