Parameterized complexity seeks a better understanding of NP-hard problems. In particular, one is interested in finding algorithms that are sufficiently fast despite (exponential) hardness in the worst case. To this end, one studies the influence of problem-specific parameters such as the solution size or certain structural input measures on the time complexity.

In addition to signing up via basis please send an email to kratsch@cs.uni-bonn.de to provide your email address (using „[Parameterized Complexity]“ as the subject). You will receive occasional notifications, (updates to) the lecture notes, and the exercise sheets via email/dropbox. Note that sending an email is not equivalent to signing up on basis and comes with no obligations.

There will be an oral exam at the end of the term. The tentative dates are August 1 and September 11, 2017. There are no requirements for admittance and the final grade is determined solely by the exam.

In the tutorials you will be given time and support to solve exercises in teams of two. Eva-Maria Hols will be present in tutorials and answer your questions or give hints. There will be essentially no presentation of solved exercises since the focus is on solving things yourself. In particular, being able to explain a solution to your neighbor is highly beneficial, and being told that „this is actually quite easy“ is much more believable coming from your neighbor. We also found that (unsurprisingly?) students are much more apt at understanding one anothers problems with a task.

Exercise sets will focus on the current chapter in the lecture and you may have more than one meeting to work one the same set. Working at home is of course encouraged too. We will not grade or proof-read your solutions, but you can verify your ideas by asking Eva-Maria during the tutorial.

There are no prerequisites other than having completed a Bachelor (typically in mathematics or computer science) or being close to doing so. Standard Bachelor lectures about algorithm design/analysis, discrete structures, logic, complexity are nevertheless beneficial.

If you do not have your Bachelor yet then you need contact the examination office to sign up for the lecture. You can still only use the grade for this course towards your Master degree.

Printer friendly versions of the slides will be made available via email/dropbox. Additional material such as proofs and illustrative sketches will be given on the board and you have to take notes yourself.

1. Techniques for obtaining so-called fixed-parameter tractable algorithms: Branching, Iterative compression, dynamic programming on tree decompositions etc.
2. Methods for proving parameterized intractability and lower bounds on parameterized running times.
3. Kernelization, i.e., studying efficient preprocessing for NP-hard problems by relating to problem parameters.

The recent book by Cygan et al. (see below) covers essentially all the material of the lecture and is highly recommended.

1. M. Cygan et al., Parameterized algorithms, Springer, 2015
2. R.G. Downey and M.R. Fellows. Fundamentals of parameterized complexity, Springer, 2013
3. R. Niedermeier, Invitation to fixed-parameter algorithms, Oxford University Press, 2006
4. J. Flum and R. Grohe, Parameterized complexity theory, Springer, 2006

All of the books make good complementary reading and each offers much more material than we could hope to cover in the lecture. Further material can be suggested if desired.