👋 Welcome to the notes and resources page for Parameterized Complexity, a MOOC offering on the Swayam/NPTEL platform. This course is offered jointly with Saket Saurabh.
We introduce the parameterized complexity paradigm and describe how this perspective allows us to formally capture the complexity of the notion of preprocessing algorithms.
We discuss algorithms based on depth-bounded search trees. These algorithms typically involve coming up with a recursive approach to the problem, where the depth of recursion is bounded by a function of the parameter.
VC above LP
We explore a clever algorithmic technique called iterative compression, which allows us to come up with FPT algorithms by gradually improving on initially suboptimal solutions.
The focus here is to explore how we can leverage the power of randomization to come up with FPT algorithms with one-sided error (false positives). Typically, the algorithms we discuss here are easy to describe and implement, but ensuring a reasonable probability of success involves a non-trivial analysis.