# 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 (either oral or written) will likely be in Mid-February. To be admitted to the exam, you need at least 1/3 of all points in the assignment sheets. You are eligible for a re-exam if and only if you take the main exam but do not pass. |

# News

- Okt 16: Assignment 01 is available (with a corrected first exercise!)

# 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)

Date | Teacher | Topic | Reference |
---|---|---|---|

Oct 16 | Holger | Intro & Kernelization | 1, 2.2.1 |

Oct 18 | Holger | Kernelization | 2.5, 2.6 |

Oct 23 | Karl | Bounded Search Trees | 3 |

Oct 25 | Cornelius | Tutorial: Assignment 1 | |

Oct 30 | Iterative Compression | 4 | |

Nov 01 —Holiday— | |||

Nov 06 | Color Coding | 5.2 | |

Nov 08 | Tutorial: Assignment 2 | ||

Nov 13 | Derandomization | 5.6 | |

Nov 15 | Miscellaneous | 6 | |

Nov 20 | Pathwidth | 7 | |

Nov 22 | Tutorial: Assignment 3 | ||

Nov 27 | Treewidth, Courcelle's Theorem | 7 | |

Nov 29 | (Holger) | Bidimensionality | 7 |

Dec 04 | Cuts and Separators | 8 | |

Dec 06 | Tutorial: Assignment 4 | ||

Dec 11 | Karl | Cuts and Separators | 8 |

Dec 13 | (Karl) | Algebraic Methods | 10 |

Dec 18 | Algebraic Methods | 10 | |

Dec 20 | Tutorial: Assignment 5 | ||

—Winter break— | |||

Jan 08 | Holger | Cut & Count | 11.2 |

Jan 10 | Tutorial: Assignment 6 | ||

Jan 15 | Representative Sets | 12.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 05 | Holger | 4-apx for treewidth | |

Feb 07 | Tutorial: Assignment 8 |