CS60083 Parameterized Algorithms Autumn 2025

Instructor:

 Sudeshna Kolay (skolay@cse.iitkgp.ac.in)

Teaching Assistant:

 Koustav De (koustavde7@kgpian.iitkgp.ac.in)

Course overview:
  Parameterized complexity theory lays out a framework with which one can carry out a refined analysis of hard algorithmic problems. It allows us to measure the complexity not only in terms of the input size, but also in terms of the additional parameter, which, being a numerical value may depend on the input arbitrarily. We generally assume that the parameter is comparatively small. Downey and Fellows developed parameterized complexity theory in a series of groundbreaking articles in the early 1990s. Since then, interested researchers have extensively contributed and have been able to come up with fascinating results. In this course, we will try to introduce comprehensive state-of-the-art tools and techniques that students can use in their future research and studies.

Classes:
 Venue: CSE-108. Timings: Monday (11:00-11:55), Tuesday (08:00-09:55)

Grading:
 Assignment: 10%, Presentation: 10%, Mid-Sem: 30%, End-Sem: 50%

Slides:
21.07.2025 L1 - Intro
22.07.2025 L2 - Branching
28.07.2025 - 29.07.2025 L3 - Kernelization (Refer to Chapter 2 and 9 from the book)
04.08.2025 - 12.08.2025 L4 - Iterative Compression
25.08.2025 - 26.08.2025 L5 - Color Coding
01.09.2025 - 09.09.2025 L6 - Misc tools
06.10.2025 - 07.10.2025 L7 - Treewidth
13.10.2025 - 14.10.2025 L8 - Alg
03.11.2025 - 04.11.2025 L10 - Whardness
10.11.2025 - 11.11.2025 L11 - ETH LB



Announcements:


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]