Week 4 · Randomization and color coding

Randomized fixed-parameter algorithms lead into color coding, random separation and derandomization.

Lectures

• Introduction to Randomized Algorithms via a Simple Randomized FPT Algorithm for FVS

• Color Coding for Longest Path

• Chromatic Coding for Feedback Arc Set on Tournaments

• Random Separation and Subgraph Isomorphism

• Derandomization

Official NPTEL lecture index