Course Objective
This is an advanced level course on the design and analysis of algorithms for computational intractable problems. There are two major objectives of this course. The first is to provide a comprehensive introduction to the field of parameterized algorithms and complexity. This includes an illustration of the key techniques for the design and analysis of fixed-parameter tractable algorithms and a demonstration of the notion of fixed-parameter intractability. The second goal of this course is to present some of the recent tools and techniques (like the framework for proving lower bounds, meta theorems, non-trivial applications of combinatorial min-max results and use of matroids) and prepare the students for research in this area of algorithm design.
Learning Outcomes
After the successful completion of this course, the students will be able to study the parameterized complexity of a given problem. In particular, they would be equipped to classify parameterized problems as being fixed-parameter tractable or intractable. They would be able to design parameterized algorithms (or show hardness) using vanilla versions or extended/modified variants of the various techniques taught in the course. They would also be able to state open problems in the area and their current complexity statuses.
Syllabus
Introduction: Review of NP-hardness, approaches to NP-hardness, motivation to parameterized algorithms, notion of fixed-parameter tractability, formal definitions of the key concepts. (2 lectures)
Basic toolkit: Kernelization, branching and bounded-depth search trees, iterative compression, greedy localization. (7 lectures)
Kernelization Techniques: Crown decomposition, sunflower lemma, expansion lemma, kernels based on linear programming. (7 lectures)
Randomized methods: Randomness in parameterized algorithms, the color coding technique, the chromatic coding technique, basic pseudo-random objects and derandomization. (8 lectures)
Treewidth: Parameterized algorithms based on dynamic programming over tree decomposition, computing/approximating treewidth. (8 lectures)
Lower bounds: Notion of fixed-parameter intractability, W-hierarchy, notion of parameterized reductions and examples, kernelization lower bounds. (8 lectures)
Textbook
- Parameterized Algorithms by M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Springer International Publishing, 2015. ISBN: 978-3-319-21275-3.
Reference
- Fundamentals of Parameterized Complexity by R. Downey and M. R. Fellows. Springer-Verlag London, 2013. ISBN: 978-1-4471-5559-1.
- Parameterized Complexity Theory by J. Flum and M. Grohe. Springer-Verlag Berlin Heidelberg, 2006. ISBN: 978-3-540-29953-0.
Past Offerings
- Offered in Jan-May, 2024 by Krithika Ramaswamy
- Offered in Jan-May, 2021 by Krithika
- Offered in July-Dec, 2019 by Krithika
Course Metadata
| Item | Details |
|---|---|
| Course Title | Parameterized Algorithms |
| Course Code | CS5003 |
| Course Credits | 3-0-0-3 |
| Course Category | PME |
| Proposing Faculty | Krithika Ramaswamy |
| Approved on | Senate 6 of IIT Palakkad |
| Course prerequisites | A first course in the design and analysis of algorithms |
| Course status | New |