Kernelization of packing problems

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 -S et M atching for integers d ≥ 3 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. Recently, Bodlaender et al. [ICALP 2008], Fortnow and Santhanam [STOC 2008], Dell and Van Melkebeek [STOC 2010] 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 lower bounds for the kernelization of d -S et M atching and other packing problems. Our bounds are tight for d -S et M atching: It does not have kernels with O ( k d−∊ ) edges for any ∊ > 0 unless the hypothesis fails. By reduction, this transfers to a bound of O ( k d − 1 − ∊ ) for the problem of finding k vertex-disjoint cliques of size d in standard graphs. It is natural to ask for tight bounds on the kernel sizes of such graph packing problems. We make first progress in that 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. This does not quite match the best lower bound of O ( k 2−∊ ) that we can prove. Most of our lower bound proofs follow a general scheme that we discover: To exclude kernels of size O ( k d −∊ ) 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 [STOC 2010] with shorter elementary arguments.

Authors

• Holger Dell
• Dániel Marx

Keywords

No keywords are indexed for this paper.