CS5440 Parameterized Algorithms (Jul-Dec 2019)



In the classical complexity the running time of an algorithm is measured as function of input length. But for many combinatorial problems inputs are structured and have multiple parameters associated with them. In parameterized algorithms we analyse the running time on multiple parameters of the input. This led to developments of various algorithmic techniques. In this course we explore various techniques to design parameterized algorithms and the accompanying hardness theory.

Prerequisites: Undergraduate Algorithms and Descrete Structures

Lecture timings: 17:30-19:00 on Tuesdays and 16:00-17:30 on Wednesdays.

Venue: C-LH7



References
  1. Parameterized Algorithms by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh (Free copy available here for personal use)
  2. Kernelization: Theory of Parameterized Preprocessing by Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi.
 Evaluation
  1. Assignments and/or presentation
  2. Quizzes

Lectures

  1. 06/08 : Lectute 1: Introdoction to FPT and Kernelization, para-NP-Hard, branching algorithms
  2. 07/08 : Lectute 2: Branching and iterative compression techniques (Feedback Vertex Set)
  3. 13/08 : No class
  4. 14/08 : Lecture 3: Feedback Vertex Set in Tournaments using iterative compression
  5. 20/08 : Lecture 4: Odd Cycle Transversal using iterative compression
  6. 21/08 : Lecture 5: Kernel for Feedback Arc Set in Tournaments and Crown decomposition
  7. 27/08 : Lecture 6: Crown decomposition, Linear kernels for V.C and MaxSAT, Color Coding (k-Path)
  8. 28/08 : Lecture 7: Color Coding (SUBISO on bounded degree graphs), Chromatic coding
  9. 04/09 : Examination 1.
  10. 11/09 : Lectute 8: Derandomization of chromatic coding
  11. 17/09 : Lecture 9: Path decomposition and DP over them, and Tree decomposition
  12. 18/09 : Lecture 10: DP over tree decomposition and MSO
  13. 24/09 : Lecture 11: FPT approximation algorithm for treewidth
  14. 25/09 : Lecture 12: Cops and robber games, brambles and grid minor theorems
  15. 15/10 : Lecture 13: Applciations of grid minor theorems, Bidimensionality theory
  16. 16/10 : Lecture 14: Shifting technique, SUBISO and Min Bisection on planar graphs
  17. 22/10 : Lecture 15: Introduction to Matroids
  18. 23/10 : Lecture 16: Linear representation of various matroids and representative family
  19. 29/10 : Lecture 17: Representative family, size bound, computation
  20. 30/10 : Lecture 18: Application of representative family
  21. 04/11 : Examination 2.
  22. 05/11 : Lecture 19: Important Separators, upper bound and computation
  23. 06/11 : Lecture 20: Application of important separators
  24. 13/11 : Lecture 21: Lowerbound, FPT-reductions, and W-hardness
  25. 13/11 : Presentation 1: Bisection of Bounded Treewidth Graphs by Convolutions by Karthik R
  26. 16/11 : Presentation 2: A Sub-exponential FPT Algorithm for Minimum Directed Bisection on Semicomplete Digraphs by Udit Maniyar
  27. 16/11 : Lecture 22: Dominating Set on Tournaments, introduction to ETH and SETH
  28. 19/11 : Lecture 23: ETH: applications in classical and parameterized complexity
  29. 20/11 : Presentation 3: Parameterized streaming algorithms by Sidharth Mohla
  30. 20/11 : Lecture 24: Kernel Lower bounds, cross composition and applcation
  31. 23/11 : Lecture 25: Parameter preserving transformations and Summary of the course
  32. 03/12 : Final Examimation