NPTEL : NOC:Parameterized Algorithms (Computer Science and Engineering)

Co-ordinators : Prof. Neeldhara Misra


Lecture 1 - Invitation to FPT

Lecture 2 - Formalizing FPT

Lecture 3 - Kernelization: High Degree Rule

Lecture 4 - Kernelization: d-Hitting Set

Lecture 5 - Kernelization: Crown Reduciton

Lecture 6 - Kernelization: Nemhauser-Trotter and Expansion Lemma

Lecture 7 - Introduction to Branching

Lecture 8 - Analyzing Recurrences

Lecture 9 - High-Degree Branching for FVS

Lecture 10 - Vertex Cover above LP

Lecture 11 - Applications of Vertex Cover above Matching

Lecture 12 - Iterative Compression I: Setting Up the Method

Lecture 13 - Iterative Compression II: Vertex Cover and Tournament Feedback Vertex Set

Lecture 14 - Iterative Compression III: Feedback Vertex Set and 3-Hitting Set

Lecture 15 - Iterative Compression IV: Odd Cycle Transversal

Lecture 16 - Introduction to Randomized Algorithms via a Simple Randomized FPT Algorithm for FVS

Lecture 17 - Color Coding for Longest Path

Lecture 18 - Chromatic Coding for Feedback Arc Set on Tournaments

Lecture 19 - Random Separation and Subgraph Isomorphism

Lecture 20 - Derandomization

Lecture 21 - Divide and Conquer and Separator

Lecture 22 - Towards Defining Treewidth

Lecture 23 - Treewidth and Constructing Treedecomposition of Few Graph Classes

Lecture 24 - Structural Properties of Treedecomposition and Win-Win

Lecture 25 - Nice Tree Decomposition and Algorithm for Max Weight Independent Set

Lecture 26 - Dynamic Programming Algorithm over graphs of Bounded Treewidth

Lecture 27 - FPT Appproximation Algorithm for Computing Tree Decomposition - Part 1

Lecture 28 - FPT Appproximation Algorithm for Computing Tree Decomposition - Part 2

Lecture 29 - FPT Appproximation Algorithm for Computing Tree Decomposition and Applications - Part 1

Lecture 30 - FPT Appproximation Algorithm for Computing Tree Decomposition and Applications - Part 2

Lecture 31 - Dynamic Programming Over Subsets for Set Cover

Lecture 32 - Dynamic Programming Over Subsets for Steiner Tree

Lecture 33 - ILP for Envy-Free Allocations and Lobbying

Lecture 34 - ILP for Imbalance Parameterized by Vertex Cover

Lecture 35 - Important Cuts: Basic

Lecture 36 - Important Cuts: Enumeration and Bounds

Lecture 37 - FPT Algorithm for Multiway Cut

Lecture 38 - FPT Algorithm for Directed Feedback Edge Set

Lecture 39 - Algebraic Techniques: Inclusion Exclusion (Coloring)

Lecture 40 - Algebraic Techniques: Inclusion Exclusion (Hamiltonian Path)

Lecture 41 - Algebraic Techniques: Matrix Multiplication

Lecture 42 - Algebraic Techniques: Polynomial Method

Lecture 43 - Matroids: Representative Sets

Lecture 44 - Matroids: Representative Sets - Computation and Combinatorics

Lecture 45 - Matroids: Representative Sets - Applications (Paths and Kernels)

Lecture 46 - Matroids: Representative Sets - Applications (Directed Long Cycle)

Lecture 47 - Reductions - An Introduction

Lecture 48 - Reductions - Problems as Hard as Clique I (Clique on Regular Graphs)

Lecture 49 - Reductions - Problems as Hard as Clique (PVC, MCC, MIS)

Lecture 50 - Reductions - Problems as Hard as Clique (Dominating Set, Set Cover)