  Kernelization algorithms are polynomial-time reductions from a problem to
itself that guarantee their output to have a size not exceeding some bound. For
example, d-Set Matching for integers d>2 is the problem of finding a matching
of size at least k in a given d-uniform hypergraph and has kernels with O(k^d)
edges. Bodlaender et al. [JCSS 2009], Fortnow and Santhanam [JCSS 2011], Dell
and Van Melkebeek [JACM 2014] developed a framework for proving lower bounds on
the kernel size for certain problems, under the complexity-theoretic hypothesis
that coNP is not contained in NP/poly. Under the same hypothesis, we show tight
lower bounds for the kernelization of d-Set Matching and other packing
problems.
  Our bounds are tight for d-Set Matching: It does not have kernels with
O(k^{d-{\epsilon}}) edges for any {\epsilon}>0 unless the hypothesis fails. By
reduction, this transfers to a bound of O(k^{d-1-{\epsilon}}) for the problem
of finding k vertex-disjoint cliques of size d in standard graphs. Obtaining
tight bounds for graph packing problems is challenging: We make first progress
in this direction by showing non-trivial kernels with O(k^2.5) edges for the
problem of finding k vertex-disjoint paths of three edges each. If the paths
have d edges each, we improve the straightforward O(k^{d+1}) kernel to a
uniform polynomial kernel where the exponent of the kernel size is independent
of k.
  Most of our lower bound proofs follow a general scheme that we discover: To
exclude kernels of size O(k^{d-{\epsilon}}) for a problem in d-uniform
hypergraphs, one should reduce from a carefully chosen d-partite problem that
is still NP-hard. As an illustration, we apply this scheme to the vertex cover
problem, which allows us to replace the number-theoretical construction by Dell
and Van Melkebeek [JACM 2014] with shorter elementary arguments.
