Parameterized Algorithms Dániel Marx, Roohani Sharma

News

11.01.2022

Exercise sheet #4

The fourth exercise sheet is available here. The deadline is January 18.

04.01.2022

No lecture on January 4

As it was announced during the last lecture, there will be no lecture on January 4, 2022.

30.11.2021

Exercise sheet #3

The third exercise sheet is available here. The deadline is December 07.

09.11.2021

Exercise sheet #2

The second exercise sheet is available here. The deadline is November 16.

26.10.2021

Exercise sheet #1

The first exercise sheet is available here. The deadline is November 2.

19.10.2021

Zoom link

The Zoom link for the lecture (starting 10:15 on every Tuesday):

https://cs-uni-saarland-de.zoom.us/j/95438071574?pwd=RFpGdXVydFJqMXQrU2w5NnVyQzg1UT09

Show all
 

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    
October 26  L02: Introduction II Slides Video  2.1, 2.2.1, 3.5, 5.1, 5.2 Sheet 1 November 02
November 02  L03: Introduction III Slides Slides Video  4, 6.1    
November 09  L04: Lower bounds Slides Video 13.1, 13.2, 13.3, 13.6, 14.1, 14.2, 14.3 Sheet 2 November 16
November 16  L05: Kernelization I Slides Video 2.1,2.2, 2.6    
November 23  L06: Kernelization II Slides Video 2.3.1,2.4, 2.5    
November 30  L07: Kernelization III Slides Slides Video 9.1,15.1,15.2.2 Sheet 3 December 07
December 07  L08: Algebraic Methods Slides (slide 19 has been updated)Video  10.1.1,10.1.2,10.4.1    
December 14  L09: Representative sets and matroids Slides Video 12.1, 12.1.1, 12.1.2, 12.1.3, 12.3, 12.3.1, 12.3.1 No sheet  
January 11  L10: Important Cuts Slides Video 8.1, 8.2, 8.3, 8.5, 8.6 Sheet 4 January 18

Reference Textbook

"Parameterized Algorithms" by Cygan et al. (see this for free pdf of the book from the authors).

 

 



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators