max planck institut
mpii logo Minerva of the Max Planck Society


Seminar in Parameterized Algorithms and Complexity (WS 10/11)

Jiong Guo, Danny Hermelin and Magnus Wahlström

First meeting: Tuesday 26.10.2010 (2nd week of the semester), 14-16, building E1.3 room 016
Time: Mondays 16:30-18:00 (note new time)
Room: E1.7 (new Cluster bulding) room 323
Prerequisites: Basic knowledge of algorithms and complexity theory (e.g., NP-completeness) is helpful.
Registration: Please send an email to the instructors if you want to secure a place. (Also remember to eventually use the University HISPOS system.)
Content: Basics of FPT and techniques for designing parameterized algorithms. To the extent of time, we will also try to cover the so-called parameterized complexity theory, to illustrate the border between parameterized tractability and intractability.
Date Lecturer Topic
26.10. Danny Hermelin Introduction
15.11. Goran Doychev Bounded Search Trees
22.11. Sebastian Ott Kernelization 1: Vertex Cover (Nemhauser-Trotter)
29.11. Praveen Chundi Kernelization 2: Problems on Planar Graphs
06.12. Oliver Nalbach Tree Decomposition (a.k.a. treewidth) Dynamic Programming
13.12. Manish Kumar Narang Color Coding
03.01. Magnus Wahlström Introduction to Parameterized Intractability
10.01. Wenkai Dai Iterative Compression
17.01. Vijay Ingalalli W[1]-hardness proofs
24.01. Yash Raj Shrestha Kernelization Lower Bounds
31.01. Joachim Luts Max Ones SAT (parameterized complexity dichotomy)
07.02. Marvin Künnemann Graph minors in FPT
14.02. Aram Harutyunyan Time Complexity of d-Hitting Set

Literature: The seminar will be given mostly based on research papers, but if you want a written treatment of the subject, see the books of Rolf Niedermeier and of Jörg Flum and Martin Grohe.