期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We introduce a new form of composition called \emph{weak composition} that allows us to obtain polynomial kernelization lower-bounds for several natural parameterized problems. Let d2 be some constant and let L1L201\N be two parameterized problems where the unparameterized version of L1 is \NP-hard. Assuming \coNP\NP\poly , our framework essentially states that composing t L1-instances each with parameter k, to an L2-instance with parameter kt1dkO(1) , implies that L2 does not have a kernel of size O(kd−) for any 0. Using this tool, we derive the following lower-bounds for kernel sizes when the parameter is the solution size k (assuming \coNP\NP\poly ):
\begin{itemize}
\item \textsc{d-Set Packing}, \textsc{d-Set Cover}, \textsc{d-Exact Set Cover}, \textsc{Hitting Set with d-Bounded Occurrences}, and \textsc{Exact Hitting Set with d-Bounded Occurrences} have no kernels of size O(kd−3−) for any 0.
\item \textsc{Kd Packing} and \textsc{Induced K1d Packing} have no kernels of size O(kd−4−) for any 0.
\item \textsc{d-Red-Blue Dominating Set} and \textsc{d-Steiner Tree} have no kernels of sizes O(kd−3−) and O(kd−4−), respectively, for any 0.
\end{itemize}
To obtain these lower-bounds, we first prove kernel lower bound for the \textsc{d-Bipartite Regular Perfect Code} parameterized by the solution size k, and then reduce from it using linear parametric transformations. Our results give a negative answer to an open question raised by Dom, Lokshtanov, and Saurabh~[ICALP2009] regarding the existence of \emph{uniform polynomial kernel} for the problems above. Up to a polylogarithmic factor, all our lower bounds transfer automatically to compression lower bounds, a notion defined by Harnik and Naor~[SICOMP2010] to study the compressibility of \NP\ instances with cryptographic applications. We believe weak composition can be used to obtain polynomial kernelization lower bounds for other interesting parameterized problems.
