zbMATH — the first resource for mathematics

Lower bounds for kernelizations and other preprocessing procedures. (English) Zbl 1268.68084
Ambos-Spies, Klaus (ed.) et al., Mathematical theory and computational practice. 5th conference on computability in Europe, CiE 2009, Heidelberg, Germany, July 19–24, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03072-7/pbk). Lecture Notes in Computer Science 5635, 118-128 (2009).
Summary: We first present a method to rule out the existence of strong polynomial kernelizations of parameterized problems under the hypothesis \(\text{P} \neq \text{NP}\). This method is applicable, for example, to the problem SAT parameterized by the number of variables of the input formula. Then we obtain improvements of related results in [H. L. Bodlaender et al., Lect. Notes Comput. Sci. 5125, 563–574 (2008; Zbl 1153.68554); L. Fortnow and R. Santhanam, in: Proceedings of the 40th annual ACM symposium on theory of computing, Victoria, Canada, STOC’08. New York, NY: Association for Computing Machinery. 133–142 (2008; Zbl 1231.68133)] by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that \(\text{PH} \neq \Sigma^{\text{P}}_3\), i.e., 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(1)} \cdot |x|^{1 - \epsilon}\) (here \(\epsilon \) is any given real number greater than zero).
For the entire collection see [Zbl 1192.68004].

68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI
[1] Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 563–574. Springer, Heidelberg (2008) · Zbl 1153.68554 · doi:10.1007/978-3-540-70575-8_46
[2] Chang, R., Kadin, Y.: On computing boolean connectives of characteristic functions. Math. Systems Theory 28, 173–198 (1995) · Zbl 0827.68065 · doi:10.1007/BF01303054
[3] Chen, Y., Flum, J.: On parameterized path and chordless path problems. In: Proceedings of the 22nd IEEE Conference on Computational Complexity (CCC 2007), pp. 250–263 (2007) · doi:10.1109/CCC.2007.21
[4] Chen, Y., Flum, J.: Subexponential time and fixed-parameter tractability: exploiting the miniaturization mapping. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol. 4646, pp. 389–404. Springer, Heidelberg (2007) · Zbl 1179.68060 · doi:10.1007/978-3-540-74915-8_30
[5] Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)
[6] 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 2008), pp. 133–142. ACM, New York (2008) · Zbl 1231.68133
[7] Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Annals of Pure and Applied Logic 130, 3–31 (2004) · Zbl 1062.03032 · doi:10.1016/j.apal.2004.01.007
[8] Grandjean, E., Kleine-Büning, H.: SAT-problems and reductions with respect to the number of variables. Journal of Logic and Computation 7(4), 457–471 (1997) · Zbl 0882.68075 · doi:10.1093/logcom/7.4.457
[9] Grohe, M.: Private communication (2008)
[10] Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News 38(1) (2007) · doi:10.1145/1233481.1233493
[11] 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 2006), pp. 719–728 (2006) · Zbl 1207.68162 · doi:10.1109/FOCS.2006.54
[12] Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences 63, 512–530 (2001) · Zbl 1006.68052 · doi:10.1006/jcss.2001.1774
[13] Johnson, D.: Announcements, updates, and greatest hits. Journal of Algorithms 8(3), 438–448 (1987) · Zbl 0633.68022 · doi:10.1016/0196-6774(87)90021-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.