Parameterized complexity is a branch of computational complexity that provides tools for tackling NP-hard problems. Rather than measuring complexity solely in terms of input size, parameterized complexity offers a more refined analysis in which the running time of an algorithm is expressed as a function of both the input size and one or more parameters. When these parameters are expected to be small, algorithms that are polynomial in the input size but exponential in the parameter(s) can still be considered tractable, since the exponential behavior is confined to the small parameter(s).

In this presentation, we will introduce the theory of parameterized complexity. We will survey the classical techniques used in the design of parameterized algorithms and then move on to structural parameterizations, focusing in particular on treewidth, one of the most successful and widely used structural parameters. Finally, we will discuss notions of parameterized hardness, including W-hardness and fine-grained complexity.