News
Exercise sheet #3Written on 20.11.24 by Dániel Marx The third exercise sheet is available here. The deadline is November 26. |
Tutorial Session #2Written on 18.11.24 by Jakob Greilhuber The second tutorial session will take place on November 20 at 16:00 in room 021 in the E1 4 building (Max Planck Institute for Informatics). |
Lecture Dates and RoomsWritten on 12.11.24 by Daniel Neuen On November 26 and January 14 there will be no lecture. Also, on November 19 and December 3 the lecture takes place in room 0.21 (right next to the usual lecture room). |
Exercise sheet #2Written on 05.11.24 by Dániel Marx The second exercise sheet is available here. The deadline is November 12. |
Tutorial Session #1Written on 22.10.24 by Jakob Greilhuber The first tutorial session will take place on November 7 at 14:00 in room 023 in the E1 4 building (Max Planck Institute for Informatics). |
Exercise sheet #1Written on 22.10.24 (last change on 29.10.24) by Dániel Marx The first exercise sheet is available here. The deadline is October 29. |
Parameterized Algorithms
This course is about designing fast algorithms for NP-hard graph theoretic problems, where the running time depends on multiple parameters of the input. For example, while a database may contain a very large amount of data, the size of the database queries is typically extremely small in comparison. The aim would be to obtain algorithms that have a small dependence on the database size, but possibly a larger dependence on the query size. Such an algorithm would be fast when the queries are small. Similarly, if the goal is to find small solutions in a large graph, then an algorithm with exponential dependence on the size of the solution and polynomial dependence on the size of the graph might be acceptable.
We will see several algorithmic techniques to design fast algorithms for NP-hard problems in this setting, called Fixed-Parameter Tractable (FPT) algorithms, as well as an overview of the lower-bound methods. We will also learn about preprocessing or data-reduction algorithms in this setting, called Kernelization algorithms, which run in polynomial time and reduce a given instance of a NP-hard problem to an equivalent but much smaller instance.
Some example topics that will be covered during the course:
- Branching, bounded-depth search trees
- Randomization, color coding
- Iterative compression
- Kernelization, sunflower lemma, crown decomposition
- Kernelization lower bounds
- Algebraic methods, inclusion-exclusion
- Representative sets and matroids
- Important cuts
- Treewidth, bidimensionality on planar graphs
- Turing and lossy kernelization
Format
Two hours of lectures every week and two hours of tutorials every other week. During the semester, 5 homework exercise sheets will be handed out, to be submitted in one week. 50% of all points on the exercise sheets are needed to be admitted to the (oral) exam. The solutions of the exercises are discussed in the tutorial sessions (after the deadline).
Lectures: Tuesday, 10:15-12:00
Tutorial: To be decided
First lecture: October 15, 2024
Room: building E1 4, room 0.24
Prerequisites
Basic knowledge of algorithms, graph theory and probability will be assumed.
| Date | Topic | Material | Reference (see below) | Exercise | Due |
|---|---|---|---|---|---|
| October 15 | L01: Introduction I | Slides | 1, 3.1, 3.2 | ||
| October 22 | L02: Introduction II | Slides | 1, 2.1, 2.2.1, 3.1, 3.2, 3.3, 3.5, 5.1, 5.2 | Sheet 1 | October 29 |
| October 29 | L03: Introduction III | Slides | 6.1, 4.1, 4.2, 4.3.1, 4.4 | ||
| November 5 | L04: Complexity of parameterized problems | Slides | 13.1, 13.2, 13.3, 13.6, 14.1, 14.2, 14.3 | Sheet 2 | November 12 |
| November 12 | L05: Kernelization I | Slides | 2.1, 2.2, 2.6 | ||
| November 19 | L06: Kernelization II | Slides | 2.3,2.4,2.5,3.4 | Sheet 3 | November 26 |
Reference Textbook
"Parameterized Algorithms" by Cygan et al. (see this for free pdf of the book from the authors).