EN
Place

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.