Course notes

In the lecture on September 1st (see slides), we discussed motivation for parameterized algorithms and relation to Operation Research. Then we looked at the preprocessing rules for Vertex Cover as in Chapter 1 of the textbook.

In the lecture on September 3rd (see slides), we discussed dynamic programming and in particular the algorithm for Steiner tree, see also Chapter~6.1.2 from the textbook.

The first exercise sheet was given out. Please prepare solutions until Wednesday next week.

In the lecture on September 10th, we discussed solutions to the first exercise set. For the dynamic programming exercise, see also Dynamic Program for Vertex Coloring.

In the lecture on September 11rd, we recalled basics from complexity theory by discussing the complexity questions from the first exercise sheet.

The second exercise sheet was given out. Please prepare solutions until Wednesday next week.

The lecture on September 17th unexpectedly did not happen.

In the lecture on September 18th, we started with the topic Kernelization and Preprocessing (see slides). We covered Chapters 2.1 (formal definitions), 2.2.1 (Vertex Cover), and 2.2.3 (Edge Clique Cover) from the textbook. In the second half, we discussed solutions to exercise sheet 2.

The third exercise sheet was given out. Please prepare solutions until Friday next week.

In the lecture on September 23rd, we had the second part of topic Kernelization and Preprocessing (see slides). We covered Chapter 2.6 (Sunflower Lemma) from the textbook and the role of preprocessing in practice on integer linear programming, based on Wolsey Chapter 7.6.

Please note the annoncement regarding the project on ItsLearning.

In the lecture on September 26th, we discussed exercise sheet 3. Then started with the topic branching (see slides). We covered Chapter 3.0 (formalism of branching) and Chapter 3.1 (Vertex Cover) from the textbook. We didn’t get to the algorithm for Closest String yet.

In the lecture on September 30rd, we finished the example on Closest String, see slides), from Chapter 3.5 of the textbook.

We practiced ILP modelling on examples from the second exercise sheet.

Topic of the lecture on October 1st was Branch-and-Bound, see slides. This does not appear in the main textbook. For reference, see Chapter 7 in Wolseley’s book.

In the lecture on October 6th, we discussed an kernel for Vertex Cover based on the LP relaxation, see slides, which follows Chapter 2.5 of the textbook.

In the lectures on October 7th and October 9th, we looked at FPT algorithms for integer linear programs, specifically the Eisenbrand-Weismantel algorithm, see slides and more slides. We also looked at an application for Closest String, see exercises. This is based on relatively new research that came out after the textbook appeared. As additional material see the lecture notes.

In the lecture on October 21th, we discussed the Exponential Time Hypothesis and a reduction from Clique to 3-SAT. The reduction appears indirectly in the textbook (via the 3-colorability problem). For the direct proof, see lecture notes.

In the lectures on October 23th, we have seen the proof of the Sparsification Lemma (for 3-SAT). The proof is omitted in the textbook, but you can find them in the lecture notes.