## 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**.