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.

The topic of this week were parameterized reductions. Based on ETH there is evidence that the Clique problem does not have an FPT algorithm. In the lecture on November 4th we reduced Clique to Set Packing and we reduced Clique to Multicolored Clique and Multicolored Clique to Hitting Set. See Chapter 13.2 for similar reductions. In the lecture on November 6th, we reduced Multicolored Clique to Exact Unique Hitting Set and the latter to k-SUM. The textbook contains in Chapter 13.6.3 hardness of Exact Unique Hitting Set, although implicitly through other reductions.

In the lectures on November 10th (slides) and November 11th (more slides), we introduced the notions of path decomposition, path width and we looked at dynamic programming approaches over path decompositions on the example of Maximum Weight Independent Set. We also looked at an application in Order Picking. We only discussed the main ideas of the DP there, but did not go over the details of the recurrence. We then generalized the notions to tree decomposition and treewidth. For reference, see Chapters 7.0-7.3 of the textbook.

The sixth exercise sheet was given out. Please prepare solutions until Tuesday next week.

In the lectures on November 18th, we discussed the solutions to the exercise sheet. For the full dynamic program including the proof of correctness, please see textbook Chapter 7.3.1.

In the lecture on November 20th, we discussed Courcelle’s Theorem, see slides. This follows the material from the textbook Chapter 7.4.

In the lectures on November 25th, we introduced the concept of randomization in algorithms and obtained an FPT algorithm for longest path using the technique of Color Coding, see slides or textbook Section 5.2.

In the lecture on November 27th, we discussed a randomized exponential time algorithm for k-SAT, see slides and the Strong Exponential Time Hypothesis (SETH). For SETH and its relation to ETH, see also textbook section 14.1.

In the lectures on December 2nd, we introduced the field of fine-grained complexity and showed hardness of Orthogonal Vectors and Diameter under SETH, see slides. On December 4th we will continue with other consequences of SETH, namely an overview of results for Subset Sum and String problems.

For a gentle introduction to the field and proofs for hardness of Orthogonal Vectors and Pattern Matching, see notes by Karl Bringmann. For hardness of Diameter, see also lecture notes by Amir Abboud.