Week 1 · Kernels and fixed-parameter tractability

The opening lectures introduce fixed-parameter tractability and develop preprocessing rules through Vertex Cover and Hitting Set.

Lectures

• Invitation to FPT

• Formalizing FPT

• Kernelization: High Degree Rule

• Kernelization: d-Hitting Set

• Kernelization: Crown Reduciton

• Kernelization: Nemhauser-Trotter and Expansion Lemma

Official NPTEL lecture index