On the Infeasi­bility of Polynomial Kernel­ization

A professor wants 6 popular guests out of 25 at a party: does a small dominating set exist? In my master's thesis talk, I use examples like this one to introduce kernelization (polynomial-time preprocessing that shrinks an instance to a size bounded by a parameter) and ask when polynomial-size kernels cannot exist. I cover the composition and distillation framework, polynomial parameter transformations, and worked examples (weighted satisfiability, Disjoint Factors, and Vertex-Disjoint Cycles). I also look at ways around the barrier, such as the many polynomial kernels for out-branchings with many leaves, and at some open problems.