TY - JOUR

T1 - Point line cover

T2 - The easy kernel is essentially tight

AU - Kratsch, Stefan

AU - Philip, Geevarghese

AU - Ray, Saurabh

N1 - Publisher Copyright:
© 2016 ACM.

PY - 2016/4

Y1 - 2016/4

N2 - 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 polynomialtime 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(nlog 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.

AB - 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 polynomialtime 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(nlog 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.

KW - Kernelization lower bounds

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=84968760304&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84968760304&partnerID=8YFLogxK

U2 - 10.1145/2832912

DO - 10.1145/2832912

M3 - Article

AN - SCOPUS:84968760304

SN - 1549-6325

VL - 12

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 3

M1 - 40

ER -