MTL780: Parameterized Algorithms for NP-hard Problems

3 Credits (3-0-0)
Pre-requisites: MTL342 or COL351

Review of NP-completeness and reductions. Introduction to parameterized complexity, parameterized algorithms through bounded search trees, iterative compression, randomized methods in parameterized algorithms, dynamic programming over subsets, treewidth and parameterized algorithms for bounded treewidth graphs, algebraic techniques in parameterized complexity, Matroids and representative sets, lower bounds for parameterized algorithms based on Exponential Time Hypothesis and Strong Exponential Time Hypothesis.