Parameterized Algorithms (CS6101)
Teaching Group
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:
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:
Then depending on the time and interests, we will cover some of the selected advanced topics from the list below:
Textbooks
Some Practical Information
Tentative Timings (Slot J): Monday 17:00-17:50, Wednesday 14:00-15:15, and Thursday 15:30-16:45.
Room: CS 34.
Evaluation (tentative):
Expectations Regarding Academic Honesty And Usage of Inclusive Languages
- Instructor: Akanksha Agrawal
- Teaching Assistant: Vinod Shambhu Gupta
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
Tentative Timings (Slot J): Monday 17:00-17:50, Wednesday 14:00-15:15, and Thursday 15:30-16:45.
Room: CS 34.
Evaluation (tentative):
- Four exams through the course, best three of the four will be considered (the three of considered exams will have equal weightage). Dates to be released shortly. The in-class component Note the exams will be in-class with a take-home component.
Expectations Regarding Academic Honesty And Usage of Inclusive Languages
