Bachelor and Master Seminar WS2020

Seminar Kernelization

Contact

Peter Rossmanith
Jan Dreier (tcs-teaching@cs.rwth-aachen.de)
Henri Lotze (tcs-teaching@cs.rwth-aachen.de)
Daniel Mock (tcs-teaching@cs.rwth-aachen.de)
Elisabet Burjons (eburjons@inf.ethz.ch)

Content

Kernelization is the theory of efficient preprocessing algorithms. When given an instance to a problem, the goal is to reduce the size of the instance as much as possible. What is then left over is a so-called kernel, which captures the essence of the instance. For some problems such a kernel can be found and for others (under reasonable assumptions) this is not possible. There exists a rich set of algorithmic techniques for kernelization and a well established theory about which problems can and cannot be kernelized. The goal of this seminar is to make the students familiar with these results. The seminar will follow this book by Fomin et. al. The book will be available in the library.

Structure

There will be weekly meetings in which the participants give their talks

Requirements

Participants should have a keen interest in theoretical computer science, but no prior knowledge is kernelization is necessary.

Material

Slides from the kick-off meeting.

Dates

Date Topic Student
13.05.2020 Inductive Priorities Jonas Spang
13.05.2020 Crown Decomposition Simon Klemp
20.05.2020 Expansion Lemma Felix Friedberger, Jana Lemke
27.05.2020 Linear Programming Maximilian Sudmann,Konrad Ostrowski
10.06.2020 Modules Anna Perret, Niklas Berndt
17.06.2020 Sunflower Lemma Maxim Pakhomenko
17.06.2020 Matroids Dominic Meiser
24.06.2020 Greedy Packing Celina Kalus
24.06.2020 Euler's Formula Julian Schnitzler
01.07.2020 Instance Selectors Marlene Damm
01.07.2020 Polynomial Parameter Transformation Magnus Groß
08.07.2020 Polynomial Lower Bounds Mohamad Altalli
08.07.2020 Turing Kernelization Sijia Guo
15.07.2020 Lossy Kernelization Michael Nguyen

Essay

Your essay should be in English, written using LaTeX and should not exceed 8 pages (excluding references). Please use this template (or something equivalent). The deadline to hand in your essay is August 17th at 10:00.