Fixed Parameter Tractability and Algorithm Design: Kernelization (equivalence and techniques), Bounded Search Trees, Iterative Compression, Randomized Methods, Dynamic Programming on Graphs of Bounded Treewidth, Important Separators.
Complexity and Lower Bounds: FPT-Reductions, W-hierarchy ,W[1]-complete and W[2]-complete problems, Exponential Time Hypothesis, Kernelization Lower Bounds.
INSTRUCTOR
COURSE DESCRIPTION:
COURSE CODE
C25
SEMESTER
Spring
COURSE TYPE
Postgraduate (PG)
ECTS
6