CS60083 Parameterized Algorithms


Instructor:

 Palash Dey and Sudeshna Kolay

Teaching Assistants:

Akashdeep Saha

Course overview:
 Parameterized algorithms has been serving as one of the key tools in algorithm design for tackling computational hardness barriers like NP-completeness for the last 30 years. Indeed, parameterized algorithms have plenty of success stories in solving many real world instances of computationally hard problems. In this course, we will introduce a bunch of techniques for designing parameterized algorithms to the students so that they can apply it in their research whenever needed.

Previous incarnation of this course can be found here.

Classes:
Venue: CSE-120. Timings: Monday 3-4:55 PM, Tuesday 3-3:55 PM, Saturday 2:30-4 PM (for tutorial and class test)

Grading:
2 Class tests: 10%, Student presentation: 10%, Mid-semester: 30%, Final: 50%

Prerequisite:
Algorithm I; strong inclination to theoretical thinking.


Announcements:

Lectures:
August 2 Palash Dey Introduction to Parameterized Algorithms
August 8 Sudeshna Kolay Bounded Search [Slides]
August 9 -- Institute Holiday (Muharram)
August 15 -- Institute Holiday (Independence Day)
August 16 Palash Dey Kernelization: Vertex Cover, FAST, Edge Clique Cover
August 22 Kernelization: Crown Decomposition - Vertex Cover, Max-Sat, LP-based Method
August 23 Sudeshna Kolay Iterative Compression [Slides]
August 29 Sudeshna Kolay Iterative Compression: OCT
Palash Dey Randomized FPT Algorithm: FVS
Color Coding: Longest Path
August 30 Palash Dey Color Coding: d-Clustering
September 5 Sudeshna Kolay Dynamic Programming over Subsets, ILP, Robertson-Seymour Theorem
September 6
September 12 Palash Dey Treewidth: Definition, Weighted Independent Set; Lower Bound on Treewidth
September 13 Courcelle's Theorem, Bidimensionality: Planar Vertex Cover, Planar Cycle Packing


References:
  1. Parameterized Algorithms by Marek Cygan (Author), Fedor V. Fomin (Author), Łukasz Kowalik (Author), Daniel Lokshtanov (Author), Dániel Marx (Author), Marcin Pilipczuk (Author), Michal Pilipczuk (Author), Saket Saurabh (Author) [free version]
  2. Parameterized Complexity Theory by J. Flum and M. Grohe