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 CoverDominating 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.

VCFVSVC above LPOCTAlmost-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.

VCTournament FVSFVSOCT

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 PathSubgraph IsomorphismFVSFAST

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