## Abstract

The input to the NP-hard Point Line Cover problem (PLC) consists of a set V 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 V. 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 ε > 0, there is no polynomial-time algorithm that reduces every instance (P, k) of PLC to an equivalent instance with O(k^{2-ε}) 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-ε}) 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 ω(n ^{2}) bits. To get around this hurdle we build on work of Goodman, Pollack and Sturmfels (STOC 1989) and devise an oracle communication protocol of cost O(n log n) for PLC; its main building blocks are a bound of O(N ^{O(n)}) for the order types of n points that are not necessarily in general position and an explicit (albeit slow) algorithm that enumerates a superset of size N^{O(n)} of all possible order types of n points. 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 |

Publisher | Association for Computing Machinery |

Pages | 1596-1606 |

Number of pages | 11 |

ISBN (Print) | 9781611973389 |

DOIs | |

State | Published - 2014 |

Event | 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States Duration: Jan 5 2014 → Jan 7 2014 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 |
---|---|

Country | United States |

City | Portland, OR |

Period | 1/5/14 → 1/7/14 |

## ASJC Scopus subject areas

- Software
- Mathematics(all)