Written on 25.01.22 by Dániel Marx
The fourth exercise sheet is available here. The deadline is February 1.
Written on 11.01.22 by Dániel Marx
The fourth exercise sheet is available here. The deadline is January 18.
Written on 04.01.22 by Dániel Marx
As it was announced during the last lecture, there will be no lecture on January 4, 2022.
Written on 30.11.21 (last change on 30.11.21) by Roohani Sharma
The third exercise sheet is available here. The deadline is December 07.
Written on 09.11.21 by Dániel Marx
The second exercise sheet is available here. The deadline is November 16.
Written on 26.10.21 by Dániel Marx
The first exercise sheet is available here. The deadline is November 2.
Written on 19.10.21 by Dániel Marx
The Zoom link for the lecture (starting 10:15 on every Tuesday):
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.
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
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.2||No sheet|
|January 11||L10: Important Cuts||Slides Video||8.1, 8.2, 8.3, 8.5, 8.6||Sheet 4||January 18|
|January 18||L11: Treewidth I||Slides Video||7.1-7.4|
|January 25||L12: Treewidth II||Slides Video||11.2.1,14.5.2, 13.6.2||Sheet 5||February 1|
|February 01||L13: Treewidth III||Slides Video||7.7|
|February 08||L14: Turing and Lossy Kernelization||Slides Slides Video||9.4, 23.1 and 23.4 from this book|