IIT Gandhinagar, IMSC · Computer Science

Parameterized Algorithms

Prof. Neeldhara Misra, Prof. Saket Saurabh · 50 free video lectures

This is a first course on techniques in parameterized algorithms, a paradigm of algorithm design that analyzes running time in finer detail than classical complexity theory: instead of expressing the running time as a function of the input size only, dependence on one or more parameters of the…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Invitation to FPT
  2. Formalizing FPT
  3. Kernelization: High Degree Rule
  4. Kernelization: d-Hitting Set
  5. Kernelization: Crown Reduciton
  6. Kernelization: Nemhauser-Trotter and Expansion Lemma
  7. Introduction to Branching
  8. Analyzing Recurrences
  9. High-Degree Branching for FVS
  10. Vertex Cover above LP
  11. Applications of Vertex Cover above Matching
  12. Iterative Compression I: Setting Up the Method
  13. Iterative Compression II: Vertex Cover and Tournament Feedback Vertex Set
  14. Iterative Compression III: Feedback Vertex Set and 3-Hitting Set
  15. Iterative Compression IV: Odd Cycle Transversal
  16. Introduction to Randomized Algorithms via a Simple Randomized FPT Algorithm for FVS
  17. Color Coding for Longest Path
  18. Chromatic Coding for Feedback Arc Set on Tournaments
  19. Random Separation and Subgraph Isomorphism
  20. Derandomization
  21. Divide and Conquer and Separator
  22. Towards Defining Treewidth
  23. Treewidth and Constructing Treedecomposition of Few Graph Classes
  24. Structural Properties of Treedecomposition and Win-Win
  25. Nice Tree Decomposition and Algorithm for Max Weight Independent Set
  26. Dynamic Programming Algorithm over graphs of Bounded Treewidth
  27. FPT Appproximation Algorithm for Computing Tree Decomposition - Part 01
  28. FPT Appproximation Algorithm for Computing Tree Decomposition - Part 02
  29. FPT Appproximation Algorithm for Computing Tree Decomposition and Applications - Part 01
  30. FPT Appproximation Algorithm for Computing Tree Decomposition and Applications - Part 02
  31. Dynamic Programming Over Subsets for Set Cover
  32. Dynamic Programming Over Subsets for Steiner Tree
  33. ILP for Envy-Free Allocations and Lobbying
  34. ILP for Imbalance Parameterized by Vertex Cover
  35. Important Cuts: Basic
  36. Important Cuts: Enumeration and Bounds
  37. FPT Algorithm for Multiway Cut
  38. FPT Algorithm for Directed Feedback Edge Set
  39. Algebraic Techniques: Inclusion Exclusion (Coloring)
  40. Algebraic Techniques: Inclusion Exclusion (Hamiltonian Path)
  41. Algebraic Techniques: Matrix Multiplication
  42. Algebraic Techniques: Polynomial Method
  43. Matroids: Representative Sets
  44. Matroids: Representative Sets -- Computation and Combinatorics
  45. Matroids: Representative Sets -- Applications (Paths and Kernels)
  46. Matroids: Representative Sets -- Applications (Directed Long Cycle)
  47. Reductions --- An Introduction
  48. Reductions --- Problems as Hard as Clique I (Clique on Regular Graphs)
  49. Reductions --- Problems as Hard as Clique (PVC, MCC, MIS)
  50. Reductions --- Problems as Hard as Clique (Dominating Set, Set Cover)

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Gandhinagar, IMSC.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights