Parameterized Complexity
This course is taught in English. This seminar was last offered in Winter Term 2020/21.
Description
Parameterized Complexity aims to re ne the traditional notion of NP-hardness by providing
reasons as to why certain problems are (probably) hard to solve. It does this by analyzing
algorithm performance not just depending on the instance size, but on additional parameters
of the problem such as the size of the desired solution. This often allows us to design algorithms
that have runtimes polynomial in the instance size, and super-polynomial in the observed
parameters, showing that the hardness of the problem stems not from the size of the instance but
from the size of the parameter. Such a re ned notion of complexity has driven the developement
of a large collection of theoretical breakthroughs and novel algorithmic techniques. Withing this
seminar we aim to give an accessible overview of the most prominent of these results and their
applications in designing state-of-the-art algorithms.
Requirements
We are looking for students with an interest in theoretical computer science and algorithm
design. Some of the topics to be discussed are fairly technical and experience with graph theory,
algorithm analysis, probability theory, and complexity theory will be bene cial. However, the
range of topics is quite wide, so a lack of background in some of these topics should not be an
obstacle. The seminar is open to bachelor students in CS, DS, IIW, and TM.
Tasks
The seminar will cover up to 10 topics, depending on the number of participants. Each topic
will be covered by one student, who will work through a paper or problem, give a 30 min
presentation on it and write a 1-2 page summary.
Organisation
There will be 4 sessions in total. First a meeting to discuss and assign topics, then 2 gatherings
after 3 weeks respectively and one nal day on which all presentations will be held. We're
targeting at most 10 participants. The exact dates are still to be determined.
Topics
The following is a selection of potential topics to be covered in the seminar:
| Kernelization | Iterative Compression | Bounded Search Trees |
| Parameterization Above Guarantee | Tree-Width | Clique-Width |
| Color Coding | Derandomization | Parameterized Approximation |
| Courcelle's Theorem | W-hardness | n-Fold IP |
Please refer to Parameterized Algorithms by Cygan et al. for literature on the subject.
