Kernelization Lower Bounds for Finding Constant Size Subgraphs
Kernelization Lower Bounds for Finding Constant Size Subgraphs
复制标题
DOI：
10.1007/978-3-319-94418-0_19
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
T. Fluschnik;G. B. Mertzios;A. Nichterlein
中科院分区：
文献类型：
--
作者：
T. Fluschnik;G. B. Mertzios;A. Nichterlein
核化是参数化算法中的一个重要工具。给定一个带有参数的输入实例，目标是在多项式时间内计算同一问题的等价实例，使得简化实例的大小仅取决于参数，而不取决于原始实例的大小。在本文中，我们提供了第一个概念性的研究核化的限制几个多项式时间可解的问题。例如，我们考虑的问题，找到一个三角形与负的边权重参数化的最大程度的输入图的总和。我们证明了这个问题的线性时间可计算的严格内核的真正次立方的大小违反了流行的APSP猜想。
Kernelization is an important tool in parameterized algorithmics. Given an input instance accompanied by a parameter, the goal is to compute in polynomial time an equivalent instance of the same problem such that the size of the reduced instance only depends on the parameter and not on the size of the original instance. In this paper, we provide a first conceptual study on limits of kernelization for severalpolynomial-timesolvable problems. For instance, we consider the problem of finding a triangle with negative sum of edge weights parameterized by the maximum degree of the input graph. We prove that a linear-time computable strict kernel of truly subcubic size for this problem violates the popular APSP-conjecture.