__Parameterized Algorithms (CS6101)__

**Teaching Group**

Akanksha Agrawal*Instructor*:TBD*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. We will touch upon some illustrations of the basic techniques like:

- Branching
- Kernelization
- Iterative Compression
- Randomized Techniques
- Parameterized reductions and fixed-parameter intractability

Then depending on the time and interests, we will cover some of the selected advanced topics from the list below:

- 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):*

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