Parameterized Complexity

Video lecture archive (2019–present)

Course description: This page is a comprehensive and growing video archive on parameterized algorithms and complexity. It covers kernelization, branching, randomization, separators, matroids, treewidth, intractability, approximation, and related techniques.

Textbooks:  There is no course text for new materials. However, most of the material we cover can be found in the following text books.

• Kernelization: Theory of Parameterized Preprocessing (with F. V. Fomin, D. Lokshtanov, and M. Zehavi). Cambridge University of Press, 2019, ISBN: 9781107415157, https://doi.org/10.1017/9781107415157 

• Parameterized Algorithms (with M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuck and M. Pilipczuck). Springer 2015, ISBN 978-3-319-21274-6, pp. 3-555. 

Prerequisites: Mathematical maturity and comfort with undergraduate algorithms and basic probability.

Lectures

1. Lecture 00: Introduction to Parameterized Algorithms [Video]

2. Lecture 01: Kernelization 1: High Degree + Greedy [Video]

3. Lecture 02: Kernelization 2: Sunflower Lemma [Video]

4. Lecture 03: Kernelization 3: Sunflower Lemma + Dominating Set in K_{i,j}-free Graphs [Video]

5. Lecture 04: Kernelization 4: Matching Based Kernels [Video]

6. Lecture 05: Kernelization 5: Generalized Matching (Expansion Lemma) [Video]

7. Lecture 06: Branching 1: Simple Examples [Video]

8. Lecture 07: Branching 2: Branching with non-trivial measure [Video]

9. Lecture 08: Branching 3: Branching with non-trivial measure [Video]

10. Lecture 09: Branching 4: Vertex cover above LP [Video]

11. Lecture 10: Randomization in Parameterized Algorithms [Video]

12. Lecture 11: Iterative Compression and Iterative Localization [Video]

13. Lecture 12: Important Separators 1 [Video]

14. Lecture 13: Important Separators 2 [Video]

15. Lecture 14: Important Separators 3 [Video]

16. Lecture 15: Matroids 1: Basics [Video]

17. Lecture 16: Matroids 2:  Representation and Representative Families [Video]

18. Lecture 17: Matroids 3:  Algorithms to compute Representative families and its Applications [Video]

19. Lecture 18:  Matroids 4: Representative families Applications and Computation of Representative Families on General Matroids [Video]

20. Lecture 19: Parameterized Intractability 1 [Video]

21. Lecture 20: Parameterized Intractability 2 [Video]

22. Lecture 21: Parameterized Intractability 3 [Video]

23. Lecture 22: Paths, Trees and t-Decomposable Graphs [Video]

24. Lecture 23: Towards Defining Tree - Decomposable Graphs [Video]

25. Lecture 24: Tree -Decomposition and t-decomposability and relation to tree-width [Video]

26. Lecture 25: Structural Properties of Tree-Decomposition [Video]

27. Lecture 26: Algorithm to compute a constant factor tree decomposition [Video]

28. Lecture 27: Dynamic Programming Algorithms over graphs of treewidth t [Video]

29. Lecture 28: Courcelle's theorem and Planar-F-Deletion via Protrusion Decomposition [Video]

30. Lecture 29: Protrusion Decomposition, Bidimensionability and Kernels on Planar graphs [Video]

31. Lecture 30: Sub-exponential Parameterized  Algorithms [Video]

32. Lecture 31: Biclique Hardness -- 1 [Video]

33. Lecture 32: Biclique Hardness -- 2 [Video]

34. Lecture 33: Biclique Hardness -- 3 [Video]

35. Lecture 34: Lossy Kernelization (Cycle Packing) -- 1 [Video]

36. Lecture 35: Lossy Kernelization (Cycle Packing) -- 2 [Video]

37. Lecture 36: Lossy Kernelization (Cycle Packing) -- 3 [Video]

38. Lecture 37: Lossy Kernelization (Cycle Packing) -- 4 [Video]

39. Lecture 38: Monotone Local Search -- 1 [Video]

40. Lecture 39: Monotone Local Search -- 2 [Video]

41. Lecture 40: Monotone Local Search -- 3 [Video]

Video Lectures from 2017 version of the course could be found at [Video]