CS60083 Parameterized Algorithms 2020

CS60083 Parameterized Algorithms

Instructor:

Palash Dey and Sudeshna Kolay

Teaching Assistants:

Rajdeep Mukherjee

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.

Classes:
Thursday 3-4:55 PM, Friday 3-3:55 PM, Monday 8-9:30 PM

Grading:
Class tests: 40%, Assignments: 40%, Viva and Presentation: 20%

Prerequisite:
Algorithm I; strong inclination to theoretical thinking will help

Announcements:

Question papers: First class test, second class test, third class test
Fourth class test will be on November 12 (Thursday) from 3PM in CSE Moodle. The syllabus is the material covered during October 15 to November 5.
Viva will be on November 5 from 3PM.
Third class test will be on October 22 (Thursday) from 3PM in CSE Moodle. The syllabus is the material covered during October 1 to October 15.
Second class test will be on October 8 (Thursday) from 3PM in CSE Moodle. The syllabus is the material covered during September 17 to October 1.
First class test will be on September 21 from 8PM in CSE Moodle.
Microsoft Teams link for Thursday's class (3-4:55 PM): here
If you have any question in the lecture videos, then ask here
The first class will be on September 3 from 3 PM.
Join the course in CSE Moodle (find Moodle link from here)
Click here to join the course Google group. All announcements will be posted here. Write your name and roll number in the membership request message.

Students Presentation:

Aditya Anand	Kernelization for Edge Clique Cover and Maximum Satisfiability	Part 1, Part 2
N Krithick Santhosh	Expansion Lemma	Here
Neel Manish Karia	Branching Algorithm for Closest String	Here
Pittu Madhusudhan Reddy	Iterative Compression for Odd cycle transversal	Here
Prashant Shishodia	Chromatic coding algorithm for d-Clustering	Here
Arnab Maiti	FPT algorithm w.r.t treewidth for Dominating Set	Part 1, Part 2
M Kousshik Raj	FPT algorithm w.r.t treewidth for Steiner Tree	Here
Amatya Sharma	Bidemsionality (sec 7.7.1, 7.7.2)	Here

Lectures:

September 3-10 (Palash)	Lec1.1 - Introduction	Reference: Chapters 1 and 2 Exercise problems 2.2, 2.4, 2.5, 2.8, 2.12, 2.14 Submit () by September 20
	Lec1.2- Kernelization: Definition, Vertex Cover
	Lec1.3 - Kernelization: FAST
	Lec1.4- Kernelization: Crown Decomposition
September 10-17 (Sudeshna)	Lec 2.1 - Bounded Search Tree method	Reference: Chapters 3 and 4 Exercise problems 3.2, 3.2, 3.5, 3.7, 3.9, 3.24, 4.3, 4.4, 4.6, 4.9 Submit (*) by September 25
	Lec 2.2 - Iterative Compression
September 17-24 (Palash)	Lec 3.1 - Color Coding	Reference: Chapter 5 Exercise problems 5.1, 5.2, 5.3, 5.8, 5.11, 5.12 Submit () by October 2
	Lec 3.2 - Derandomization
September 24 - October 1 (Sudeshna)	Lec 4 - Misc tools	Reference: Chapter 6 Exercise problems 6.1, 6.2, 6.7, 6.14, 6.18, 6.19 Submit (*) by October 8
October 1-8 (Palash)	Lec 5.1 - Treewidth Introduction	Reference: Chapter 7 Exercise problems 7.4, 7.6, 7.8, 7.14, 7.15, 7.18, 7.19 Submit FPT algorithm for Odd Cycle Transversal in 7.18 by October 16
	Lec 5.2 - FPT Algorithm for Independent Set
	Lec 5.3 - MSO2 Logic, Courcelle’s Theorem
October 8-15 (Sudeshna)	Lec 6 - Algorithmic Technique	Reference: Chapter 10 Slides, Missing audio Exercise problems: 10.2, 10.7, 10.17, 10.18
October 15-22 (Palash)	Lec 7.1 - Introduction to W-Hardness	Reference: Chapter 13 Exercise problems: 13.3, 13.12, 13.16, 13.22, 13.23 Submit () by November 2
	Lec 7.2 - Dominating Set On Tournaments
	Lec 7.3 - W-Hierarchy
Oct 29 - Nov 5 (Sudeshna)	Lec 8 - ETH Hardness: part 1, part 2 Comment: in the last slide, I mention once that the ETH statement is about SAT. This is wrong. ETH is about 3-SAT.	Reference: Chapter 14 Exercise problems: 14.1 - 14.19 Submit this by November 5

References:

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]
Parameterized Complexity Theory by J. Flum and M. Grohe