Параметризованные алгоритмы весна 2018

Преподаватель: Близнец Иван Анатольевич (iabliznets@gmail.com)

Лекции

• 16 february. Bounded search trees.
  • FPT. Kernelization. Vertex Cover. Feedback Vertex Set. Closest String.
• 2 march. Kernelization.
  • Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability.
• 16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching.
• 23 march. Vertex Cover above Matching. Iterative Compression.
  • Odd Cycle transversal $O^*(4^k)$. Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal $O^*(3^k)$.
• 30 march. Randomized methods.
• 6 april. $O^*(4^k)$ algorithm for k-path. Derandomization.
• 13 april. Dynamic programming over subsets. Integer linear programming. Graph minors and Robertson-Seymour theorem.
• 20 april. Important cuts. Edge Multiway Cut.
• 27 april. Important cuts in Directed graphs. Directed Feedback Vertex Set.
• 04 may. W[1] class.
• 11 may. Kernel lower bounds.
• 18 may. Vertex cover does not admit subquadratic bit size kernel.

Практика

• 16 february, "Bounded search trees (HW)."

Надо оформить 5 самых сложных задач из Вами решенных.

• 2 march, "Kernelization."
• 2 march, "Kernelization(HW)."
• 16 march, "Kernelization II(HW)."
• 23 march, "Iterative Compression."
• 23 march, "Iterative Compression(HW)."
• 30 march, "Randomized methods."
• 30 march, "Randomized methods(HW)."
• 06 april, "Derandomization."
• 06 april, "Randomized methods and derandomization(HW)."
• 13 april, "Miscellaneous(HW)."
• 20 april, "Important cuts(HW)."
• 27 april, "Important cuts II."
• 27 april, "Important cuts II(HW)."
• 03 may, "W[1], W[2]."
• 03 may, "W[1], W[2](HW)."