# Parameterized Algorithms - Institution: IIT Gandhinagar IMSC - Department: Computer Science and Engineering - Taught by: Prof. Neeldhara Misra, Prof. Saket Saurabh - Level: Undergraduate - Language: English - Subjects: Computer science, Engineering - Source: [NPTEL](https://nptel.ac.in/courses/106106230) - Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.) - Syllabus: [at the source](https://nptel.ac.in/courses/106106230) - Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words) 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 input instance is taken into account. This is a fast-evolving field and a fundamental approach to coping with NP-hardness, alongside approximation and randomized algorithms. The course will be a natural follow-up to a first course in algorithms and data structures for theoretically-inclined students and those who are curious about approaches to dealing with the theoretical limitations that emerge from the theory of NP-completeness. Remark 1. A companion course might cover topics focused entirely on lower bounds (covering W-hardness, ETH and SETH-based hardness, hardness based on the UGC, and hardness of kernelization). A natural follow-up course might cover topics in the intersection of parameterized and approximation algorithms. Remark 2. Lecture videos indicative of the course content can be found at this playlist from a previous offering of this course at the Institute for Mathematical Sciences, Chennai Intended audience: Undergraduate students who have already done a basic data structures/algorithms course. Prerequisites: Data Structures and Algorithms ## Lectures 1. [Invitation to FPT](https://invisiblenetwork.ai/learn/nptel/106106230/fdfb1c5e7a05) (YouTube) 2. [Formalizing FPT](https://invisiblenetwork.ai/learn/nptel/106106230/a28c3ece7fd9) (YouTube) 3. [Kernelization: High Degree Rule](https://invisiblenetwork.ai/learn/nptel/106106230/710fee24e3cc) (YouTube) 4. [Kernelization: d-Hitting Set](https://invisiblenetwork.ai/learn/nptel/106106230/5d16ce99af18) (YouTube) 5. [Kernelization: Crown Reduciton](https://invisiblenetwork.ai/learn/nptel/106106230/34f71af23845) (YouTube) 6. [Kernelization: Nemhauser-Trotter and Expansion Lemma](https://invisiblenetwork.ai/learn/nptel/106106230/036ef73f3dd0) (YouTube) 7. [Introduction to Branching](https://invisiblenetwork.ai/learn/nptel/106106230/fb7095916e24) (YouTube) 8. [Analyzing Recurrences](https://invisiblenetwork.ai/learn/nptel/106106230/ddb656b4a7b4) (YouTube) 9. [High-Degree Branching for FVS](https://invisiblenetwork.ai/learn/nptel/106106230/18b910710649) (YouTube) 10. [Vertex Cover above LP](https://invisiblenetwork.ai/learn/nptel/106106230/30bcda9aca81) (YouTube) 11. [Applications of Vertex Cover above Matching](https://invisiblenetwork.ai/learn/nptel/106106230/b056df04cb11) (YouTube) 12. [Iterative Compression I: Setting Up the Method](https://invisiblenetwork.ai/learn/nptel/106106230/faa12f897256) (YouTube) 13. [Iterative Compression II: Vertex Cover and Tournament Feedback Vertex Set](https://invisiblenetwork.ai/learn/nptel/106106230/4b3e265fe3eb) (YouTube) 14. [Iterative Compression III: Feedback Vertex Set and 3-Hitting Set](https://invisiblenetwork.ai/learn/nptel/106106230/fac2dbcb2e80) (YouTube) 15. [Iterative Compression IV: Odd Cycle Transversal](https://invisiblenetwork.ai/learn/nptel/106106230/8a2b51d1ec5b) (YouTube) 16. [Introduction to Randomized Algorithms via a Simple Randomized FPT Algorithm for FVS](https://invisiblenetwork.ai/learn/nptel/106106230/befd97540628) (YouTube) 17. [Color Coding for Longest Path](https://invisiblenetwork.ai/learn/nptel/106106230/63b0d7a5e6f8) (YouTube) 18. [Chromatic Coding for Feedback Arc Set on Tournaments](https://invisiblenetwork.ai/learn/nptel/106106230/d39c1d446439) (YouTube) 19. [Random Separation and Subgraph Isomorphism](https://invisiblenetwork.ai/learn/nptel/106106230/0c954ac75b23) (YouTube) 20. [Derandomization](https://invisiblenetwork.ai/learn/nptel/106106230/05fe07dcd338) (YouTube) 21. [Divide and Conquer and Separator](https://invisiblenetwork.ai/learn/nptel/106106230/4d29a699d6e3) (YouTube) 22. [Towards Defining Treewidth](https://invisiblenetwork.ai/learn/nptel/106106230/df4c7d44800e) (YouTube) 23. [Treewidth and Constructing Treedecomposition of Few Graph Classes](https://invisiblenetwork.ai/learn/nptel/106106230/01784a541d81) (YouTube) 24. [Structural Properties of Treedecomposition and Win-Win](https://invisiblenetwork.ai/learn/nptel/106106230/5c7d86ae23e0) (YouTube) 25. [Nice Tree Decomposition and Algorithm for Max Weight Independent Set](https://invisiblenetwork.ai/learn/nptel/106106230/7c1d1181b6c0) (YouTube) 26. [Dynamic Programming Algorithm over graphs of Bounded Treewidth](https://invisiblenetwork.ai/learn/nptel/106106230/70028791433a) (YouTube) 27. [FPT Appproximation Algorithm for Computing Tree Decomposition - Part 01](https://invisiblenetwork.ai/learn/nptel/106106230/19981d1368d2) (YouTube) 28. [FPT Appproximation Algorithm for Computing Tree Decomposition - Part 02](https://invisiblenetwork.ai/learn/nptel/106106230/74f771da894b) (YouTube) 29. [FPT Appproximation Algorithm for Computing Tree Decomposition and Applications - Part 01](https://invisiblenetwork.ai/learn/nptel/106106230/63516d7f6fb7) (YouTube) 30. [FPT Appproximation Algorithm for Computing Tree Decomposition and Applications - Part 02](https://invisiblenetwork.ai/learn/nptel/106106230/5e85a9c46766) (YouTube) 31. [Dynamic Programming Over Subsets for Set Cover](https://invisiblenetwork.ai/learn/nptel/106106230/765a218779ad) (YouTube) 32. [Dynamic Programming Over Subsets for Steiner Tree](https://invisiblenetwork.ai/learn/nptel/106106230/c953d4abdb7d) (YouTube) 33. [ILP for Envy-Free Allocations and Lobbying](https://invisiblenetwork.ai/learn/nptel/106106230/c0539e6398e8) (YouTube) 34. [ILP for Imbalance Parameterized by Vertex Cover](https://invisiblenetwork.ai/learn/nptel/106106230/365b0f79fa2a) (YouTube) 35. [Important Cuts: Basic](https://invisiblenetwork.ai/learn/nptel/106106230/ebeeea09afa7) (YouTube) 36. [Important Cuts: Enumeration and Bounds](https://invisiblenetwork.ai/learn/nptel/106106230/5455adf71327) (YouTube) 37. [FPT Algorithm for Multiway Cut](https://invisiblenetwork.ai/learn/nptel/106106230/90f89e2e827a) (YouTube) 38. [FPT Algorithm for Directed Feedback Edge Set](https://invisiblenetwork.ai/learn/nptel/106106230/f5aba00843c0) (YouTube) 39. [Algebraic Techniques: Inclusion Exclusion (Coloring)](https://invisiblenetwork.ai/learn/nptel/106106230/5fced87a3cbd) (YouTube) 40. [Algebraic Techniques: Inclusion Exclusion (Hamiltonian Path)](https://invisiblenetwork.ai/learn/nptel/106106230/b5950001f3e2) (YouTube) 41. [Algebraic Techniques: Matrix Multiplication](https://invisiblenetwork.ai/learn/nptel/106106230/fd2e92c5aa04) (YouTube) 42. [Algebraic Techniques: Polynomial Method](https://invisiblenetwork.ai/learn/nptel/106106230/bd8ecb1f9bba) (YouTube) 43. [Matroids: Representative Sets](https://invisiblenetwork.ai/learn/nptel/106106230/2d9f7000def8) (YouTube) 44. [Matroids: Representative Sets -- Computation and Combinatorics](https://invisiblenetwork.ai/learn/nptel/106106230/97dcbb04ec3b) (YouTube) 45. [Matroids: Representative Sets -- Applications (Paths and Kernels)](https://invisiblenetwork.ai/learn/nptel/106106230/621dd8a4ca3b) (YouTube) 46. [Matroids: Representative Sets -- Applications (Directed Long Cycle)](https://invisiblenetwork.ai/learn/nptel/106106230/4f81f1b1dbb1) (YouTube) 47. [Reductions --- An Introduction](https://invisiblenetwork.ai/learn/nptel/106106230/c847470943a2) (YouTube) 48. [Reductions --- Problems as Hard as Clique I (Clique on Regular Graphs)](https://invisiblenetwork.ai/learn/nptel/106106230/71754014cb8e) (YouTube) 49. [Reductions --- Problems as Hard as Clique (PVC, MCC, MIS)](https://invisiblenetwork.ai/learn/nptel/106106230/3b8b8650634f) (YouTube) 50. [Reductions --- Problems as Hard as Clique (Dominating Set, Set Cover)](https://invisiblenetwork.ai/learn/nptel/106106230/c0209de6f7fb) (YouTube)