文章基本信息

标题：Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization
本地全文：下载
作者：Danny Hermelin, Xi Wu
期刊名称：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.
关键词：composition, Kernelization Lower Bounds, Parameterized Complexity