Lower Bounds for Kernelizations
Yijia Chen, Jörg Flum, Moritz Müller · 2007
ABSTRACT. We first present a method to rule out the existence of strong polynomial kernelizations of parameterized problems under the hypothesis P �NP. For example, this method is applicable to the problem SAT parameterized by the number of variables of the input formula. Then we obtain further improvements of corresponding results in [5, 7] by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that the polynomial hierarchy does not collapse to its third level, we show that every parameterized problem with a “linear OR ” and with NP-hard underlying classical problem does not have polynomial reductions to itself that assign to every instance x with parameter k an instance y with |y|�k O · |x | −ε (here ε is any given real number greater than zero). 1.