Lower Bounds on Kernel­ization

Preprocessing shows up everywhere in practice, and kernelization gives it a theoretical footing: shrink an instance in polynomial time to a size bounded by some function of a parameter. Some NP-hard problems shrink all the way to polynomial size, but many apparently do not. I show how those negative results are proved. A composition packs many instances into one with a small parameter. Combined with a polynomial kernel, it would give a distillation, which would collapse the polynomial hierarchy. Polynomial parameter transformations spread the hardness further. The examples include weighted satisfiability, Disjoint Factors, and Vertex-Disjoint Cycles, and I also discuss ways around the barrier and open problems.