max planck institut

informatik

informatik

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:

**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.**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.**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.

Lectures | Tuesdays and Thursdays, 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 must join the
mailing list on or before April 30, 2015. |

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 |

Assignments | There will be three sets of assignments to hand in. Each set accounts for 10% of the final grade. |

Examination | The course has two exams: one mid-semester test and one final exam. The mid-semester test accounts for 30% of the final grade, the final exam for the remaining 40%. 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: Tuesday, June 16, 09.00 - 12.00, E1.4 Room 021. Final exam: Tuesday, August 4, 9.00 - 12.00, E1.4 Room 021. Re-exam: Tuesday, September 22, 09.00 - 12.00, E1.4 Room 021. |

Note that the schedule is dense during the first half of the
semester, and not so much during the second half.

Topics on future dates are tentative.

Date | Lecture | Tutorial | Assignment |
---|---|---|---|

21 Apr | Introduction | ||

23 Apr | Branching | Tutorial | |

28 Apr | Iterated Compression | ||

30 Apr | Color Coding | Tutorial | |

5 May | Important Separators | ||

7 May | Tutorial | Assignment I | |

12 May | Assignment I | ||

14 May | No class: Ascension | ||

19 May | Treewidth I | ||

21 May | Treewidth II | Tutorial | |

26 May | Graph Minors I | ||

28 May | Graph Minors II | Tutorial | |

2 Jun | Assignment II | ||

4 Jun | No class: Corpus Christi | Assignment II | |

9 Jun | Kernelization I | ||

11 Jun | Tutorial | ||

16 Jun | Mid-Semester Test | ||

18 Jun | Tutorial | ||

23 Jun | |||

25 Jun | |||

30 Jun | |||

2 Jul | Kernelization II | ||

7 Jul | |||

9 Jul | Kernelization III | Tutorial | |

14 Jul | Lower Bounds I | ||

16 Jul | Tutorial | Assignment III | |

21 Jul | Assignment III | ||

23 Jul | Lower Bounds II | Tutorial | |

28 Jul | |||

30 Jul | Lower Bounds III | Tutorial |