HSE theory of computing, lecture 10: parameterized complexity, FPT, kernels and vertex cover

- Examples of better time bounds for brute force searches - Solving vertex clover in time (1.4645)^k * poly(n) time - Definition of the class FPT - Examples of the kernel technique - Mathematical definition of a kernel - See lecture notes for the proof that a kernel exists if and only if the problem is FPT Course website: http://wiki.cs.hse.ru/Theory_of_computation_2025