👋 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.
Class Plan
Introduction & Kernelization
Week 01
We introduce the parameterized complexity paradigm and describe how this perspective allows us to formally capture the complexity of the notion of preprocessing algorithms.
Vertex Cover
Dominating Set
Branching Algorithms
Week 02
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
FVS
VC above LP
OCT
Almost-2-SAT
Iterative Compression
Week 03
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.
VC
Tournament FVS
FVS
OCT
Randomized Methods
Week 04
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.
Long Path
Subgraph Isomorphism
FVS
FAST
Treewidth - I
Week 05
Treewidth - II
Week 06
Miscellaneous Techniques
Week 07
Important Separators
Week 08
Treewidth Revisited
Week 09
Algebraic Methods
Week 10
Matroids
Week 11
Lower Bounds
Week 12