Multivariate Algorithmics
Advanced Course, 3+1
Basic Information
| Lecturers: | Karl Bringmann and Holger Dell |
|---|---|
| Lectures: | Tuesday + Thursday, 16:15 - 18:00, Room 024 E1 4 |
| Tutorials: | Every other Thursday |
| First Session: | October 16th, 2018 |
| Assistants: | Cornelius Brand and Marc Roth |
| Credits: | 6 CP (≃ 4 hours/week in class + 4 hours/week for exercise sheets) |
| Prerequisites: | We assume basic knowledge in algorithms and theoretical computer science. Therefore, required prerequisites are a basic lecture in algorithms (such as "Grundzüge von Algorithmen und Datenstrukturen") and a basic lecture in in theoretical computer science (such as "Theoretische Informatik"). The core lecture "Algorithms and Data Structures" would be helpful, but is not a formal requirement. |
| Exam: | The exam will be written and take place on February 18 at 10:00-12:00 in E1 3, room SR016. You may bring a handwritten two-sided cheat sheet. To be admitted to the exam, you need at least 1/3 of all points in the assignment sheets. If you are admitted to the exam, then you will also be admitted to the re-exam and can improve your grade. The re-exam will be written and take place on March 19 at 10:00-12:00 in E1 1, room SR106. |
News
- Oct 16: Assignment 01 is available (with a corrected first exercise!)
- Oct 23: Assignment 02 is available
- Nov 06: Assignment 03 is available
- Nov 20: Assignment 04 is available
- Dec 4: Assignment 05 is available
- Dec 18: Assignment 06 is available
- January 8: Assignment 07 is available
- The exam will be written. There will be a trial exam.
- January 30: Assignment 08 is available
- The exam has been graded. You can learn your grade and see your exam by going to the assistants' office (Room 426 Campus E1 3).
- The re-exam will be written too (on March 19 at 10-12). If you choose to take the re-exam, you must register with us until March 3rd by sending an email to Karl. Also don't forget to register in HISPOS.
Description
This course is about fast algorithms for NP-hard problems. The approach is to measure the running time of an algorithm as a function of not just the input length, but 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.
You will learn many different intriguing algorithmic techniques to deal with NP-hard problems when a secondary input parameter is small. You will be brought to the cutting edge of current research in the area of multivariate algorithmics. You will also learn about complexity results which for some computational problems show that algorithms with a faster running time may be impossible even when the chosen secondary parameter is relatively small.
Literature
The course will be based on the book "Parameterized Algorithms" by Cygan et al. (see this for a pdf). The references in the schedule below refer to chapters in this book.
Other books on the topic include:
"Parameterized Complexity Theory" by Flum and Grohe
"Fundamentals of Parameterized Complexity" by Downey and Fellows
The books are also available in the library.
Schedule
(tentative)
| Date | Teacher | Topic | Reference |
|---|---|---|---|
| Oct 16 | Holger | Intro & Kernelization | 1, 2.2.1 |
| Oct 18 | Holger | Kernelization (Crown rule, LP-based) | 2.3.1, 2.5 |
| Oct 23 | Karl | Bounded Search Trees (Algorithms for Vertex Cover, Vertex Cover above LP) | 3.1, 3.4 |
| Oct 25 | Cornelius | Tutorial: Assignment 1 | |
| Oct 30 | Karl | Iterative Compression (Basic Technique, Algorithm for Feedback Vertex Set) | 4.1, 4.3.1 |
| Nov 01 —Holiday— | |||
| Nov 06 | Karl | Color-Coding (Randomized Algorithms for Feedback Vertex Set, k-Path, Subgraph Isomorphism) | 5.1, 5.2, 5.3 |
| Nov 08 | Tutorial: Assignment 2 | ||
| Nov 13 | Holger | Extensor-Coding | Sec. 1.2-3.3 of [BDH18] |
| Nov 15 | Karl | Miscellaneous (Graph Minors, Integer Programming, Steiner Tree) | 6.1.2, 6.2, 6.3 |
| Nov 20 | Holger | DP on Trees and Narrow Grids, Pathwidth | 7.1, 7.2 |
| Nov 22 | Tutorial: Assignment 3 | ||
| Nov 27 | Holger | Treewidth, Weighted Independent Set, Courcelle's Theorem | 7.2, 7.3.1, 7.4 |
| Nov 29 | Holger | Cops and Robbers, Balanced Separators, Computing Treewidth | (7.5), 7.6 |
| Dec 04 | Holger | Excluded Grid Theorem, Bidimensionality | 7.7 |
| Dec 06 | Holger | Algebraic Methods (Inclusion-Exclusion, Fast Möbius Transform, Fast Subset Convolution, Counting proper colorings) | 10.1.1, 10.2, 10.3, 10.3.1 |
| Dec 11 | Karl | Cuts and Separators (Minimum Cuts, Important Cuts, Edge Multiway Cut) | 8.1, 8.2, 8.3 |
| Dec 13 | Tutorial: Assignment 4 | ||
| Dec 18 | Karl | Cuts and Separators (Bounding the number of important cuts, Steiner Tree) | 8.2, 10.1.2 |
| Dec 20 | Karl | FPT in P (Maximum Matching by solution size, Diameter by vertex cover number) | Sec. 5 of [GMN15], Sec. A of [BHM18] |
| —Winter break— | |||
| Jan 08 | Holger | Fast Subset Convolution (Counting Perfect Matchings), Cut & Count (Steiner Tree) | 11.1.1, 11.2.1 |
| Jan 10 | Tutorial: Assignment 5 | ||
| Jan 15 | Holger | Representative Sets (Long Directed Cycles) | 12.3, 12.3.5 |
| Jan 17 | Tutorial: Assignment 6 | ||
| Jan 22 | Karl | Fixed-Parameter Intractability (Parameterized reductions, W-Hierarchy) | 13.1, 13.2, 13.3 |
| Jan 24 | Tutorial: Assignment 7 | ||
| Jan 29 | Karl | ETH lower bounds (Definition of ETH/SETH, Sparsification Lemma, Lower bounds for 3-Coloring, Clique, Odd Set) | 14.1, 14.2, 14.3.1, 14.4, 13.6.3 |
| Jan 31 | Karl | (S)ETH lower bounds (Lower bounds for Grid Tiling, Unit Disk Independent Set, Dominating Set) | 14.4.1, 14.5.3 |
| Feb 05 | Holger | Hardness of Kernelization | 15.1.1, 15.1.2 |
| Feb 07 | Tutorial: Assignment 8 | ||