Incompressibility through Colors and IDs
Incompressibility through Colors and IDs
复制标题
DOI：
10.1007/978-3-642-02927-1_32
复制
发表时间：
2009-07
期刊：
影响因子：
--
通讯作者：
M. Dom;D. Lokshtanov;Saket Saurabh
中科院分区：
文献类型：
--
作者：
M. Dom;D. Lokshtanov;Saket Saurabh
在参数化复杂性中，每个问题实例都有一个参数，如果存在多项式时间预处理规则，将输入实例减少到具有多项式墨水大小的实例，则参数化问题被称为承认多项式核。许多问题已被证明承认多项式核，但直到最近，才由Bodlaender et al.[4]和Fortnow and Santhanam[9]开发了一个证明多项式核不存在的框架。在本文中，我们展示了如何将这些结果与使用颜色和id的组合约简结合起来，以证明各种基本问题的核化下界：我们展示了由终端数量和解大小参数化的斯坦纳树问题，以及连通顶点覆盖和被容顶点覆盖问题不允许多项式核。后两个结果令人惊讶，因为密切相关的顶点覆盖问题允许大小为2k的核。Alon和Gutner在h - minor Free graph参数化为h= | h |和solution sizeand得到支配集的akpoly(h)核，并询问是否存在更小的核[2]。通过证明h -次自由图的支配集不承认大小为多项式ink+h的核，我们部分地解决了这个问题。Harnik和Naor为稀疏子集Sumproblem[13]获得了一种“压缩算法”。我们证明了他们的算法本质上是最优的，因为实例不能进一步压缩。当通过解决方案sizekand和最大集合大小参数化时，调用SetandSet Coveradmit内核sizekO(d)。我们证明了这两个问题，以及唯一覆盖和有界秩不相交集问题，都不承认多项式核。所有的结果都是在多项式层次结构不会崩溃到第三层的假设下进行的。对于上述几个问题，多项式核的存在性是文献[2,3,11,12,14]中明确提出的开放问题。我们的许多结果也排除了压缩算法的存在，压缩算法的概念类似于Harnik和Naor[13]定义的核化，用于讨论中的问题。
In parameterized complexity each problem instance comes with a parameterk, and a parameterized problem is said to admit apolynomial kernelif there are polynomial time preprocessing rules that reduce the input instance to an instance with size polynomial ink. Many problems have been shown to admit polynomial kernels, but it is only recently that a framework for showing the non-existence of polynomial kernels has been developed by Bodlaender et al. [4] and Fortnow and Santhanam [9]. In this paper we show how to combine these results with combinatorial reductions which use colors and IDs in order to prove kernelization lower bounds for a variety of basic problems:We show that theSteiner Treeproblem parameterized by the number of terminals and solution sizek, and theConnected Vertex CoverandCapacitated Vertex Coverproblems do not admit a polynomial kernel. The two latter results are surprising because the closely relatedVertex Coverproblem admits a kernel of size 2k.Alon and Gutner obtain akpoly(h)kernel forDominating Set inH-Minor Free Graphsparameterized byh= |H| and solution sizekand ask whether kernels of smaller size exist [2]. We partially resolve this question by showing thatDominating Set inH-Minor Free Graphsdoes not admit a kernel with size polynomial ink+h.Harnik and Naor obtain a “compression algorithm” for theSparse Subset Sumproblem [13]. We show that their algorithm is essentially optimal since the instances cannot be compressed further.Hitting SetandSet Coveradmit a kernel of sizekO(d)when parameterized by solution sizekand maximum set sized. We show that neither of them, along with theUnique CoverageandBounded Rank Disjoint Setsproblems, admits a polynomial kernel.All results are under the assumption that the polynomial hierarchy does not collapse to the third level. The existence of polynomial kernels for several of the problems mentioned above were open problems explicitly stated in the literature [2,3,11,12,14]. Many of our results also rule out the existence of compression algorithms, a notion similar to kernelization defined by Harnik and Naor [13], for the problems in question.