|
11:45, Lecture Hall 5 Point Line Cover: The Easy Kernel is Essentially Tight G Philip MPI, Saarbrucken. 12-01-15 Abstract 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, and the question is whether there exists a set of at most k lines which pass through all points in P. By straightforward reduction rules one can efficiently reduce any input to one with at most k^{2} 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 \epsilon>0, there is no polynomial-time algorithm that reduces every instance (P,k) of PLC to an equivalent instance with O(k^{2-\epsilon}) points. This answers, in the negative, an open problem posed by Lokshtanov (PhD Thesis, 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 (STOC 2010). 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(k^{2-\epsilon}) 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 \omega(n^{2}) bits. To get around this hurdle we use a result of Alon (Mathematika, 1986) to 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. Joint work with Stefan Kratsch and Saurabh Ray Published in the Proceedings of SODA 2014 Online version: http://arxiv.org/abs/1307.2521
|
