Multivariate Algorithmics

Advanced Course, 3+1

Basic Information

Lecturers:Karl Bringmann and Holger Dell
Lectures:Tuesday + Thursday, 16:15 - 18:00, Room 024 E1 4
Tutorials:Every other Thursday
First Session:October 16th, 2018
Assistants:Cornelius Brand and Marc Roth
Credits:6 CP (≃ 4 hours/week in class + 4 hours/week for exercise sheets)
Prerequisites:

We assume basic knowledge in algorithms and theoretical computer science. Therefore, required prerequisites are a basic lecture in algorithms (such as "Grundzüge von Algorithmen und Datenstrukturen") and a basic lecture in in theoretical computer science (such as "Theoretische Informatik"). The core lecture "Algorithms and Data Structures" would be helpful, but is not a formal requirement.

Exam:The exam will be written and take place on February 18 at 10:00-12:00 in E1 3, Room SR016. To be admitted to the exam, you need at least 1/3 of all points in the assignment sheets. If you are admitted to the exam, then you will also be admitted to the re-exam and can improve your grade. The re-exam will either be written and take place on March 20 at 10:00-12:00, or it will be a 45-minute long oral exam.

News

Description

This course is about fast algorithms for NP-hard problems. The approach is to measure the running time of an algorithm as a function of not just the input length, but 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.

You will learn many different intriguing algorithmic techniques to deal with NP-hard problems when a secondary input parameter is small. You will be brought to the cutting edge of current research in the area of multivariate algorithmics. You will also learn about complexity results which for some computational problems show that algorithms with a faster running time may be impossible even when the chosen secondary parameter is relatively small.

Literature

The course will be based on the book "Parameterized Algorithms" by Cygan et al. (see this for a pdf). The references in the schedule below refer to chapters in this book.

 

Other books on the topic include:

"Parameterized Complexity Theory" by Flum and Grohe

"Fundamentals of Parameterized Complexity" by Downey and Fellows

 

The books are also available in the library.

Schedule

(tentative)

DateTeacherTopicReference
Oct 16HolgerIntro & Kernelization1, 2.2.1
Oct 18HolgerKernelization (Crown rule, LP-based)2.3.1, 2.5
Oct 23KarlBounded Search Trees (Algorithms for Vertex Cover, Vertex Cover above LP)3.1, 3.4
Oct 25CorneliusTutorial: Assignment 1 
Oct 30KarlIterative Compression (Basic Technique, Algorithm for Feedback Vertex Set)4.1, 4.3.1
Nov 01           Holiday
Nov 06KarlColor-Coding (Randomized Algorithms for Feedback Vertex Set, k-Path, Subgraph Isomorphism)5.1, 5.2, 5.3
Nov 08 Tutorial: Assignment 2 
Nov 13HolgerExtensor-CodingSec. 1.2-3.3 of [BDH18]
Nov 15KarlMiscellaneous (Graph Minors, Integer Programming, Steiner Tree)6.1.2, 6.2, 6.3
Nov 20HolgerPathwidth7
Nov 22 Tutorial: Assignment 3 
Nov 27HolgerTreewidth, Courcelle's Theorem7
Nov 29(Holger)Bidimensionality7
Dec 04HolgerCuts and Separators8
Dec 06 Tutorial: Assignment 4 
Dec 11KarlCuts and Separators8
Dec 13(Karl)Algebraic Methods10
Dec 18 Algebraic Methods10
Dec 20 Tutorial: Assignment 5 
—Winter break
Jan 08HolgerCut & Count11.2
Jan 10 Tutorial: Assignment 6 
Jan 15 Representative Sets12.3
Jan 17 W-Hierarchy 
Jan 22(Karl)ETH lower bounds 
Jan 24 Tutorial: Assignment 7 
Jan 29 Hardness of Kernelization 
Jan 31 SETH lower bounds 
Feb 05Holger4-apx for treewidth 
Feb 07 Tutorial: Assignment 8