Parameterized Algorithms

Advanced Course, 2+1

Postponed by 4 weeks!

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.

Basic Information

Lectures:Friday 2PM to 4PM at Room E1.4 024 (tentative)
Lecturer:Daniel Marx and Pranabendu Misra
First lecture:TBA
Tutorials:TBA (Once every 2 weeks)
Assistant:Philip Wellnitz
First tutorial:TBA
Credits:5
Exam:Oral Exam
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

Description

 

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.

Schedule (lectures)

DateNotesTopicExerciseDue
  First Lecture 
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     

Schedule (tutorials)

DateTopicDiscussed
   
   
   
   
   
   
   

Announcements

Material