Point Line Cover
Point Line Cover
复制标题
DOI：
10.1145/2832912
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
Stefan Kratsch;Geevarghese Philip;Saurabh Ray
中科院分区：
文献类型：
--
作者：
Stefan Kratsch;Geevarghese Philip;Saurabh Ray
NP-硬点线覆盖问题（PLC）的输入由平面上的n个点的集合P和正整数k组成;问题是是否存在一组至多k条线穿过P中的所有点。通过简单的归约规则，可以有效地将任何输入归约为至多k2个点。我们表明，这种简单的减少已经基本上是严格的标准假设下。更准确地说，除非多项式层次结构坍缩到第三级，否则对于任何ε > 0，没有多项式时间算法可以将PLC的每个实例（P，k）减少到具有O（k2−ε）点的等价实例。这回答了Lokshtanov [2009]提出的一个公开问题。我们的证明使用了来自参数化复杂性的内核概念，以及Dell和货车Melkebeek [2010，2014]开发的用于推导内核大小下限的机制。它有两个主要成分：我们首先表明，通过减少从顶点覆盖，即-除非多项式的层次结构重叠-PLC没有总大小为O（k2-ε）位的内核。这并不直接暗示所要求保护的点数的下限，因为具有n个点的PLC实例的最公知的多项式时间编码需要ω（n2）比特。为了绕过这个障碍，我们在Alon [1986]的工作基础上，设计了一个成本为O（nlog n）的PLC的Oracle通信协议。该协议与总大小的下限（这也适用于此类协议）一起产生了点数量的规定下限。虽然一些基本上紧多项式下界的内核的总大小是已知的，我们的结果是，据我们所知，第一个显示出一个非平凡的结构/二级参数的下界。这也是第一个内核化下限的例子，它利用了戴尔和货车梅尔克贝克的工作中获得的oracle通信协议下限的全部功能。我们结合联合收割机的主要抽象思想，我们的证明，以获得一个通用的配方，可用于获得这样的下限为未知的或不够强的编码的其他问题。
The input to the NP-hard point line cover problem (PLC) consists of a set P of n points on the plane and a positive integer k; the question is whether there exists a set of at most k lines that pass through all points in P. By straightforward reduction rules, one can efficiently reduce any input to one with at most k2 points. We show that this easy reduction is already essentially tight under standard assumptions. More precisely, unless the polynomial hierarchy collapses to its third level, for any ε > 0, there is no polynomial-time algorithm that reduces every instance (P,k) of PLC to an equivalent instance with O(k2−ε) points. This answers, in the negative, an open problem posed by Lokshtanov [2009]. Our proof uses the notion of a kernel from parameterized complexity, and the machinery for deriving lower bounds on the size of kernels developed by Dell and van Melkebeek [2010, 2014]. It has two main ingredients: We first show, by reduction from vertex cover, that—unless the polynomial hierarchy collapses—PLC has no kernel of total size O(k2−ε) bits. This does not directly imply the claimed lower bound on the number of points, since the best-known polynomial-time encoding of a PLC instance with n points requires ω(n2) bits. To get around this hurdle, we build on work of Alon [1986] and devise an oracle communication protocol of cost O(n log n) for PLC. This protocol, together with the lower bound on the total size (which also holds for such protocols), yields the stated lower bound on the number of points. While a number of essentially tight polynomial lower bounds on total sizes of kernels are known, our result is—to the best of our knowledge—the first to show a nontrivial lower bound for structural/secondary parameters. It is also the first example of a lower bound for kernelization that makes use of the full power of the oracle communication protocol lower bounds that can be obtained from the work of Dell and van Melkebeek. We combine the main abstract ideas of our proof to derive a general recipe that could be used to obtain such lower bounds for other problems with unknown or insufficiently strong encodings.