https://tue.osiris-student.nl/onderwijscatalogus/extern/cursus?cursuscode=2IMA25&collegejaar=2025&taal=enStudents learn in Algorithms (2ILC0) that many computational problems are NP-hard. It is widely believed that for such problems, no algorithm exists that always finds the optimal solution efficiently (in polynomial time). One way to deal with NP-hard problems is to use approximation algorithms, as discussed in Advanced Algorithms (2IMA10), or to apply heuristics (2ILH0). However, it is of great practical and theoretical relevance to investigate under which circumstances computing exact solutions is still feasible. This leads to the concept of parameterized algorithms, and parameterized complexity. The idea is to do a more refined complexity analysis, which not only takes the input size (n) into account, but also a second parameter (k) which somehow captures the “structure” or “difficulty” of the input instance. The goal is then to develop so-called FPT algorithms, for which the exponential dependency of the running time (which is most likely unavoidable for NP-hard problems) is not on the input size n, but only on the parameter k. Such algorithms are provably efficient on “easy instances”, despite the NP-hardness of the problem. There is a wide variety of algorithmic techniques for designing FPT algorithms for NP-hard problems. However, there are also problems for which (for the given parameterization) FPT algorithms do not exist (under appropriate complexitytheoretic assumptions such as P≠NP). The goal of the course is to teach techniques to design FPT algorithms, as well as techniques that can be used to prove that FPT algorithms do not exist.After completing the course, the successful student:
- Knows the definitions of the complexity classes FPT and W[1], of a parameterized problem, of the Exponential Time Hypothesis and its Strong variant, of kernelization, and of various types of reductions.
- Can design parameterized reductions to prove the W[1]-hardness of parameterized problems.
- Can apply the algorithmic design techniques of kernelization, color coding, bounded-depth search trees, iterative compression, dynamic programming over subsets, and important separators to create exact fixed-parameter tractable algorithms for NP-hard problems.
- Can analyze the running time of parameterized algorithms using branching vectors, recurrences, and the binomial theorem to estimate the size of recursion trees.
Written ANS examination