Please note that on 11.3., the entire Saarland university has postponed the start of the semester by 4 weeks. This also affects this course. We will update the information below as soon as we can.
|Lectures:||Friday 2PM to 4PM at Room E1.4 024 (tentative)|
|Lecturer:||Daniel Marx and Pranabendu Misra|
|Tutorials:||TBA (Once every 2 weeks)|
|Prerequisites:||Basic knowledge of algorithms, graph theory and probability will be assumed.|
|Mailing List:||It is mandatory for students to signup for the course mailing list |
Please subscribe here: https://lists.mpi-inf.mpg.de/listinfo/fptalgo20
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.