Faculty
Dániel Marx is tenured Faculty at CISPA. He obtained his PhD in 2005 at the Budapest University of Technology and Economics in Hungary. After that, he had postdoc researcher and visiting researcher positions in Berlin, Budapest, and Tel Aviv. From 2012 to 2019, he was at the Institute for Computer Science and Control of the Hungarian Academy of Sciences, where he has founded the Parameterized Algorithms and Complexity group, funded from his European Research Council Starting and Consolidator Grants. In 2019, he became a senior researcher at the Max Planck Institute for Informatics in Saarbrücken, and joined CISPA as a tenured faculty member in 2020. Dániel is known for his theoretical work on algorithms and lower bounds for a wide range of problems.
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).