While many popular algorithms work in polynomial time, most of the natural problems are NP-hard, that is, (most probably) they do not admit polynomial-time algorithms. This course is dedicated to an approach that aims to overcome the NP-hardness barrier while still retaining provable guarantees on the algorithm.
More precisely, parameterized complexity achieves this by introducing another measure of the input called the parameter. The running time of the algorithm is then measured as some function of the parameter k and the input size n. The main target of the theory is a fixed-parameter tractable (FPT) algorithm, working in time f(k) · poly(n) for some function f of k. In practice, the dependency is often single-exponential in k and linear in n, leading to algorithms that are quite efficient as long as k is reasonably small. For example, while the Vertex Cover problem is NP-hard on general graphs, it admits an FPT algorithm running in time O(1.2738k + k · n), where k is the size of the vertex cover – which is still practical for pretty large graphs with a vertex cover of size up to 190.
In fact, the parameter needs not to be the solution size or something similarly explicit in the input, but rather could be an arbitrary property of the instance. A prominent example is the treewidth of a graph, which intuitively measures how tree-like the graph is. There are however, many other width measures capturing other structural properties of graphs, and in general many other ways to exploit the parameterized viewpoint to achieve tractability for a generally hard problem.
Throughout the course, we will cover most of the fundamental aspects of the parameterized complexity theory, starting from the basics and (gently) leading into currently active research topics by the end of the course. The list of topics encompasses algorithmic techniques, such as branching, linear programming, color coding, dynamic programming over various decompositions; kernelization a.k.a. parameterized preprocessing; and lower bounds, i.e., methods to rule out the existence of certain parameterized algorithms.
