Parameterized Algorithms

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. Similarly, if the goal is to find small solutions in a large graph, then an algorithm with exponential dependence on the size of the solution and polynomial dependence on the size of the graph might be acceptable.

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.

Some example topics that will be covered during the course:

• Branching, bounded-depth search trees
• Randomization, color coding
• Iterative compression
• Kernelization, sunflower lemma, crown decomposition
• Kernelization lower bounds
• Algebraic methods, inclusion-exclusion
• Representative sets and matroids
• Important cuts
• Treewidth, bidimensionality on planar graphs
• Turing and lossy kernelization

Format

Two hours of lectures every week and two hours of tutorials every other week. During the semester, 5 homework exercise sheets will be handed out, to be submitted in one week. 50% of all points on the exercise sheets are needed to be admitted to the (oral) exam. The solutions of the exercises are discussed in the tutorial sessions (after the deadline). 

Lectures: Tuesday, 10:15-12:00

Tutorial: To be decided

First lecture: April 11, 2023

Room: E 1 4 (MPI-INF) 021

Prerequisites

Basic knowledge of algorithms, graph theory and probability will be assumed.

Date	Topic	Material	Reference (see below)	Exercise	Due
April 11	L01: Introduction I	Slides	1, 3.1, 3.2, 3.3
April 18	L02: Introduction II	Slides	2.1, 2.2.1, 3.5, 5.1, 5.2	Sheet 1	April 25
April 25	L03: Introduction III	Slides	6.1, 4.1, 4.2, 4.3.1, 4.4
May 2	L04: Lower Bounds	Slides	13.1, 13.2, 13.3, 13.6, 14.1, 14.2, 14.3	Sheet 2	May 9
May 9	L05: Kernelization I	Slides	2.1, 2.2, 2.6
May 16	L06: Kernelization II	Slides	2.3.1, 2.5, 2.4
May 23	L07: Kernelization III	Slides	9.1, 15.1 (intro)	Sheet 3	May 30
May 30	L08: Kernelization Lower Bounds	Slides	15.1,15.2.2
June 6	L09: Algebraic Methods	Slides	10.1.1,10.1.2,10.4.1
June 13	No lecture
June 20	L10: Important Cuts	Slides	8.1, 8.2, 8.3, 8.5, 8.6	Sheet 4	June 27
June 20	L11: Treewidth I	Slides	7.1-7.4
July 4	L12: Treewidth II	Slides	11.2.1,14.5.2, 13.6.2
July 11	L13: Treewidth III	Slides	7.7	Sheet 5	July 18
July 18	L14: Turing and Lossy Kernelization	Slides	9.4, 23.1 and 23.4 from this book

 

Reference Textbook

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