__Parameterized Algorithms (CS6101)__

**Teaching Group**

Akanksha Agrawal*Instructor*:Sugyani Mahapatra*Teaching Assistant*:

**An Introductory Note**

**Parameterized Algorithms:**There are ample of examples from the early years of Computer Science that suggests input size is not the only governing factor in the runtime complexity of a problem. A few such examples that one can pick up from some basic Algorithms textbooks are: 1) Radix Sort , where the running time changes based how many bits we use to represent the input numbers, 2) classical graph problems on tree(-like) graphs, and 3) Minimising maximum lateness in a schedule while taking into account the number of distinct arrival times. This indicates that certain structurally useful features of the input/output may dramatically simplify the job for us. Parameterized Algorithms is precisely the study of how a secondary measure, called as the

*parameter*, affects the complexity of the problem. Some of the central objectives in this field are:

- Design efficient algorithms for the problems, where we are allowed to be slow in the parameter but we need to be very fast with respect to the input size.
- Preprocess the input to reduce its size drastically (eliminate the dependence on the input size completely).

- Rule out existence of (faster) parameterized algorithms.

We will study what parameterized algorithms is all about, and on the way learn some very exciting tools and techniques to obtain/refute algorithms. I would like to note that these techniques find wide range of applications also in different allied fields. Some of these topics are:

- Branching
- Kernelization
- Iterative Compression
- Randomized Techniques and basic pseudorandom objects used in derandomization of algorithms
- Dynamic programming over subsets
- Parameterized reductions and fixed-parameter intractability
- Matroids and their applications

If time permits, based on your interest we will also look at

**some**of the advanced topics like:

- Important separators and their applications
- Algebraic techniques
- Tree decomposition and their applications
- Subset convolution and their applications in obtaining improved dynamic programming based algorithms
- Graph Minors and Robertson-Seymour Theorem
- Exponential Time Hypothesis and its application in obtaining FPT lower bounds
- Strong Exponential Time Hypothesis and its application on refuting certain FPT and XP algorithms
- Faster exact algorithms using their FPT counterparts

**Textbooks**

- Parameterized Algorithms, Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuck, Pilipczuck, Saurabh.

**Some Practical Information**

**Monday 17:00-17:50, Wednesday 14:00-15:15, and Thursday 15:30-16:45.**

*Tentative Timings (Slot J):*

**CS 34.**

*Room:*

*Evaluation (tentative):***(25% + 25%)**Two quizzes (07/09/2023, 19/11/2023)**(50%)**Endsem Exam (16/11/2023)

**mathematically correct and easily readable**scribed lecture notes for them by volunteering in the class and by getting assigned the topic, when asked for; you can claim 5 extra marks that you can use to top-up your final marks. While creating scribed lecture notes, you can take upto three iterations in submitting the final draft, where you incorporate feedback from the TA and/or the instructor . Please note that the judgement on the correctness and ease of readability will solely lie on the instructor and no arguments will be entertained after the third draft submission. Also, you will be required to submit the final draft within 10 days of the completion of the relevant topic.

**Expectations Regarding Academic Honesty And Usage of Inclusive Languages**