## Parameterized Complexity

*This course is taught in English. This seminar was last offered in Winter Term 2020/21.*

#### Description

Parameterized Complexity aims to rene 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 rened 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 benecial. 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.