Fine-grained Parameterized Algorithms

• Course codes: M-AfgD-12-K→FPA12
• External links:
  QISMoodle

Overview

Contents

This course introduces you to the exciting areas of parameterized algorithms and fine-grained complexity theory. In these areas, we analyze the complexity of problems in more detail than just “polynomial time” and “NP-hard”. You will discover beautiful algorithmic techniques to develop algorithms that are faster than the naive brute-force approach, and you will learn to prove that certain problems probably do not have faster algorithms.

Organizational Details

• Moodle: Please register at the Moodle-Page, all further communication will be done there.
• First lecture: April 16, 2024 at 14:15.
• Time: Tue/Wed/Thu 14-16.
• Location: Room 307, Robert-Mayer-Straße 11-15, 60325 Frankfurt am Main.
• Format: In-person lectures and tutorials.
• Mandatory activities: The course has mandatory activities! They are required to be admitted to the exam. For each activity, you will receive constructive feedback and an evaluation according to the EMRN rubric. Moreover, you get several chances to be reassessed if you did not meet the expectations the first time.
  • Exercises. Every week, you will work on a problem set. You can discuss the solutions in groups beforehand, but you are not allowed to share the writing. Some problems are marked with ‼️. It is mandatory to hand in these solutions on the Moodle-Page by the following Monday at 14:00. They will be graded, but you may get the chance to revise your answers. To be admitted to the exam, you must eventually prove to us that you are at the level of Meets Expectations in every marked exercise.
  • Formal writing. On the Moodle-Page, you must hand in two solutions for any non-trivial problem of your choice (most likely from the problem sets). In this activity, we will place a much higher standard at the formality of your writing. You should use very precise formal mathematical language and reasoning, so your solution must be as formal and complete as you are able, and it must be written in LaTeX using this LaTeX-template: https://github.com/goethe-tcs/note-template. To be admitted to the exam, you must submit two written solutions and receive at least Meets Expectations on both submissions.
  • Oral presentations. We expect that you present several times throughout the semester. For example, you must present at least twice a solution to an exercise during the tutorial session, and at least once a topic from the lecture (typically a proof from the book). Blackboard presentations are welcome. To be admitted to the exam, you must receive at least Meets Expectations on two presentations.
  • Revisions. If you received Revision Needed in an activity, you can still earn Meets Expectations by revising your answers in writing - we discuss your revision orally and your evaluation may get updated. If you receive Not Assessable, you must individually meet with the senior staff to discuss your learning progress, and you will be re-assessed on the same material (likely with a different task) at a later point during the semester.
• Exam: The final exam is an oral exam. Since you are only admitted to the exam if you have completed all mandatory activities, the purpose of the oral exam is to verify that (1) your submissions are your own work, and (2) that you can explain important concepts and proofs that were covered in the lectures.
• Time commitment: 10 ECTS with 25h each = 250h. Subtracting 50 hours of exam preparation, we arrive at 14h per week. Of these, 4h are lectures, 2h are exercise groups, and 8h are self-study.

Learning goals

After the course, you will be able to

• describe and compare various complexity assumptions in parameterized algorithms and fine-grained complexity,
• reproduce important results, algorithms, and proof techniques from the area,
• analyze the complexity of parameterized algorithms, develop new algorithms for similar problems, and prove correctness and hardness results,
• assess the power and limitations of the methods of the area.

Weekplan

This is a preliminary weekplan. It will be updated as the course progresses.

• 15. April – 19. April1 Introduction to Parameterized Algorithms: Vertex-Cover, Kernelization
  Cygan et al., Chapter 1+2 · Problem set
• 22. April – 26. April2 Bounded-search trees
  Cygan et al., Chapter 3 · Problem set
• 29. April – 3. May3 Iterative Compression and Randomized Algorithms
  Cygan et al., Chapter 4 · Cygan et al., Chapter 5 · Problem set
• 6. May – 10. May4 Dynamic Programming Techniques: Pathwidth, Treewidth, Tree Decompositions, Courcelle's Theorem
  Cygan et al., Chapter 7 · Problem set
• 13. May – 17. May5 Treewidth: Computing Treewidth, Cops and Robber, Graph Minor Theorem, Win/Win-Algorithms
  Cygan et al., Chapter 7 · Problem set
• 20. May – 24. May6 Algebraic Algorithms I: Inclusion-Exclusion, Möbius Transform, Subset Convolution
  Cygan et al., Chapter 10 · Problem set
• 27. May – 31. May7 Algebraic Algorithms II: k-Path
  Cygan et al., Chapter 10 · Problem set
• 3. June – 7. June8 Recap: no new material
• 10. June – 14. June9 Fixed-Parameter Intractability: Parameterized reductions, Clique, Independent Set, Vertex Cover, W-Hierarchy
  Cygan et al., Chapter 13
• 17. June – 21. June10 Introduction to Fine-grained Complexity: Schoening's Algorithm for k-CNF-SAT, Strong Exponential Time Hypothesis (SETH), Orthogonal Vectors
  Bringmann/Künnemann, Chapter 1+2
• 24. June – 28. June11 The Polynomial Method: Fast Matrix Multiplication, Fast Multivariate Polynomial Evaluation, Razborov/Smolensky
  Bringmann/Künnemann, Chapter 4
• 1. July – 5. July12 The Polynomial Method for APSP
  Bringmann/Künnemann, Chapter 5
• 8. July – 12. July13 TBD: to be determined
• 15. July – 19. July14 Final Week: no new material

Literature and Links

• This course was taught in WiSe 2020/21 with videos.
• Cygan et al. “Parameterized Algorithms” [preprint pdf • e-UB • ISBN 978-3-319-21274-6].
• A previous iteration of this course: Multivariate Algorithmics (2018).
• Lecture notes of the course by Bringmann and Künnemann at Saarland University [url]
• Flum and Grohe “Parameterized Complexity Theory” (2006).
• Downey and Fellows “Fundamentals of Parameterized Complexity” (2013).
• Parameterized complexity course by Dániel Marx and Pranabendu Misra.