# Basic Information

Lectures: (Online) Friday 2PM to 4PM at Room E1.4 024 (tentative) Daniel Marx and Pranabendu Misra May 8, 2020 Tuesday, 14:15 (Once every 2 weeks) Philip Wellnitz May 19 5 Oral Exam Basic knowledge of algorithms, graph theory and probability will be assumed. 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)

DateTopicMaterialReference (see below)ExerciseDue
May 8L01: Introduction ISlides  VideoCh. 1, 2.1, 2.2, 3.1, 3.2, 3.3, 5.2Sheet 1 (L01)May 15
May 15L02: Introduction IISlides  VideoCh. 4, 6.1
May 22L03: Lower BoundsSlides  VideoCh. 13.1, 13.2, 13.3, 13.6, 14.1, 14.2, 14.3Sheet 2 (L02 + L03)May 29
May 29L04: Kernelization ISlides  VideoCh. 2.1, 2.2.1, 2.2.2, 2.3.2, 2.4, 2.6, 9.1
June 5L05: Kernelization IISlides  VideoCh. 2.3, 2.5, 9.3, 15.1, 15.2.2Sheet 3 (L04 + L05)June 12
June 12L06: Algebraic MethodsSlides  VideoCh 10.1, 10.1.2, 10.4, 10.4.1
June 19L07: Treewidth ISlides  VideoCh. 7.1-7.4, 14.5.2
June 26L08: Treewidth IISlides  VideoCh. 7.7Sheet 4 (L07 + L08)July 3
July 3L09: Important CutsSlides  VideoCh. 8.1, 8.2, 8.3, 8.5, 8.6Sheet 5 (L09)July 10
July 10L10: MatroidsCh. 12.1, 12.3, 12.6
July 17

L11: Turing Kernels and Lossy Kernels

Slides  VideoCh. 9.4, [LPRS]

# Material

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

[LPRS]: Lossy Kernelization - STOC 2017 [arxiv]