Teaching

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.

Schedule:

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.