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
September 19 -- Mid-Semester Break
September 20
September 26
September 27
October 3 -- Institute Holiday
October 4
October 10 Sudeshna Kolay Algebraic Techniques [Slides]
October 11 Palash Dey Parameterized Reductions
October 17 Parameterized Reduction for FVS on Tournaments, W-hardness
October 18 Sudeshna Kolay ETH and SETH based Hardness
October 24 -- Diwali
October 25 -- Second Class Test
October 31 -- Students' Presentations
November 1 -- Students' Presentations


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