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
SODA 2022 - ACM/SIAM Symposium on Discrete AlgorithmsSODA 2022 - ACM/SIAM Symposium on Discrete Algorithms
SODA
Journal of the ACM
ICALP
ICALP 2021ICALP 2021
PODS
PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database SystemsJune 202140th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database System
UNSPECIFIED
2nd Symposium on Foundations of Responsible Computing (FORC 2021)2nd Symposium on Foundations of Responsible Computing, FORC 2021, June 9-11, 2021, Virtual Conference
Journal of the ACM
SIAM Journal on Computing
ESA
28th Annual European Symposium on Algorithms (ESA 2020)ESA 2020
ESA
28th Annual European Symposium on Algorithms (ESA 2020)ESA 2020
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).