Faculty
Dr. Dániel Marx ist tenured Faculty am CISPA. Er promovierte 2005 an der Budapest University of Technology and Economics in Ungarn. Danach hatte er Postdoc- und Gastforscherpositionen in Berlin, Budapest und Tel Aviv. Von 2012 bis 2019 war er am Institute for Computer Science and Control der Hungarian Academy of Sciences, wo er die Gruppe Parameterized Algorithms and Complexity gründete. Förderung erhielt er durch einen ERC Starting und Consolidator Grant. 2019 wurde er leitender Wissenschaftler am Max-Planck-Institut für Informatik in Saarbrücken und wechselte 2020 als tenured Faculty ans CISPA. Dániel ist bekannt für seine theoretischen Arbeiten zu Algorithmen und unteren Grenzwerten für eine Vielzahl an Problemen.
SODA
ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
SODA
ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
IPEC
17th International Symposium on Parameterized and Exact Computation (IPEC 2022)17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
IPEC
17th International Symposium on Parameterized and Exact Computation (IPEC 2022)17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
IPEC
17th International Symposium on Parameterized and Exact Computation (IPEC 2022)17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Journal of Computer and System Sciences
IPEC
17th International Symposium on Parameterized and Exact Computation (IPEC 2022)17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
WG
48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG2022)48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG2022)
ESA
30th Annual European Symposium on Algorithms (ESA 2022)30th Annual European Symposium on Algorithms (ESA 2022)
SoCG
38th International Symposium on Computational Geometry (SoCG 2022)38th International Symposium on Computational Geometry (SoCG 2022)
Parameterized Algorithms
This course is about designing fast algorithms for NP-hard graph theoretic problems, where the running time depends on multiple parameters of the input. For example, while a database may contain a very large amount of data, the size of the database queries is typically extremely small in comparison. The aim would be to obtain algorithms that have a small dependence on the database size, but possibly a larger dependence on the query size. Such an algorithm would be fast when the queries are small.
We will see several algorithmic techniques to design fast algorithms for NP-hard problems in this setting, called Fixed Parameter Tractable (FPT) algorithms, as well as an overview of the lower-bound methods. We will also learn about preprocessing or data-reduction algorithms in this setting, called Kernelization algorithms, which run in polynomial time and reduce a given instance of a NP-hard problem to an equivalent but much smaller instance.
Format
Two hours of lectures every week and two hours of tutorials every other week.
Lectures: Tuesday, 10:15-12:00, online over Zoom
First lecture: October 19, 2021
Prerequisites
Basic knowledge of algorithms, graph theory and probability will be assumed.
| Date | Topic | Material | Reference (see below) | Exercise | Due |
|---|---|---|---|---|---|
| October 19 | L01: Introduction I | Slides Video | 1, 3.1, 3.2, 3.3 |
Reference Textbook
"Parameterized Algorithms" by Cygan et al. (see this for free pdf of the book from the authors).