# Fine-grained Parameterized Algorithms

**SoSe 2024**

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

### 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, KernelizationCygan 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** - 6. May
–
10. May4
**Dynamic Programming Techniques:**Pathwidth, Treewidth, Tree Decompositions, Courcelle's TheoremCygan et al., Chapter 7 · Problem set - 13. May
–
17. May5
**Treewidth:**Computing Treewidth, Cops and Robber, Graph Minor Theorem, Win/Win-AlgorithmsCygan et al., Chapter 7 · Problem set - 20. May
–
24. May6
**Algebraic Algorithms I:**Inclusion-Exclusion, Möbius Transform, Subset ConvolutionCygan et al., Chapter 10 · Problem set - 27. May
–
31. May7
**Algebraic Algorithms II:**k-PathCygan 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-HierarchyCygan 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 VectorsBringmann/Künnemann, Chapter 1+2 - 24. June
–
28. June11
**The Polynomial Method:**Fast Matrix Multiplication, Fast Multivariate Polynomial Evaluation, Razborov/SmolenskyBringmann/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.