Plays in YouTube's player, loaded from youtube-nocookie.com when you press Play. Watch on YouTube

Learn · Parameterized Algorithms

Lecture 6 of 50Week 1

Kernelization: Nemhauser-Trotter and Expansion Lemma

Prof. Neeldhara Misra and Prof. Saket Saurabh · IIT Gandhinagar IMSC

Credits and licence

From
Parameterized Algorithms, IIT Gandhinagar IMSC (at NPTEL)
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge. Coordinated by IIT Madras.
Who can watch
Tweens profiles and older. How courses are placed

All the lectures

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