Abstract
We first present a method to rule out the existence of parameter non-increasing polynomial kernelizations of parameterized problems under the hypothesis P≠NP. This method is applicable, for example, to the problem Sat parameterized by the number of variables of the input formula. Then we obtain further improvements of corresponding results in (Bodlaender et al. in Lecture Notes in Computer Science, vol. 5125, pp. 563–574, Springer, Berlin, 2008; Fortnow and Santhanam in Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC’08), ACM, New York, pp. 133–142, 2008) 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 self-reductions that assign to every instance x with parameter k an instance y with |y|=k O(1)⋅|x|1−ε (here ε is any given real number greater than zero). We give various applications of these results. On the structural side we prove several results clarifying the relationship between the different notions of preprocessing procedures, namely the various notions of kernelizations, self-reductions and compressions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP’08, Track A). Lecture Notes in Computer Science, vol. 5125, pp. 563–574. Springer, Berlin (2008)
Chang, R., Kadin, Y.: On computing boolean connectives of characteristic functions. Math. Syst. Theory 28, 173–198 (1995)
Chen, Y., Flum, J.: On parameterized path and chordless path problems. In: Proceedings of the 22nd IEEE Conference on Computational Complexity (CCC’07), pp. 250–263 (2007)
Chen, Y., Flum, J.: Subexponential time and fixed-parameter tractability: exploiting the miniaturization mapping. J. Log. Comput. 19(1), 89–122 (2009)
Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51–229 (2006)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)
Fortnow, L., Santhanam: Infeasibility of instance compression and succinct PCPs for NP. In: Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC’08), pp. 133–142. ACM, New York (2008). Full version available at: http://lance.fortnow.com/papers/. Accessed 23 May 2010
Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Log. 130, 3–31 (2004)
Grandjean, E., Kleine-Büning, H.: SAT-problems and reductions with respect to the number of variables. J. Log. Comput. 7(4), 457–471 (1997)
Grohe, M.: Private communication (2008)
Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News 38(1) (2007)
Harnik, D., Naor, M.: On the compressibility of NP instances and cryptographic applications. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 719–728 (2006). Full version appears as TR06-022 in ECCC Reports 2006, available at http://eccc.hpi-web.de/year/2006/. Accessed 23 May 2010
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 512–530 (2001)
Johnson, D.: Announcements, updates, and greatest hits. J. Algorithms 8(3), 438–448 (1987)
Müller, M.: Parameterized randomization. PhD thesis, Albert-Ludwigs-Universität Freiburg i.Br. URN: urn:nbn:de:bsz:25-opus-64017. Available at http://www.freidok.uni-freiburg.de/volltexte/6401/ (2009). Accessed 23 May 2010
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)
Yap, C.K.: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26, 287–300 (1983)
Author information
Authors and Affiliations
Corresponding author
Additional information
M. Müller wishes to thank the John Templeton Foundation for its support under Grant #13152, The Myriad Aspects of Infinity.
Rights and permissions
About this article
Cite this article
Chen, Y., Flum, J. & Müller, M. Lower Bounds for Kernelizations and Other Preprocessing Procedures. Theory Comput Syst 48, 803–839 (2011). https://doi.org/10.1007/s00224-010-9270-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-010-9270-y