👋 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