Point line cover: the easy kernel is essentially tight

DOI10.1145/2832912MaRDI QIDQ4962617zbMATH OpenOpenAlexFDO

Authors Stefan Kratsch, Geevarghese Philip, Saurabh Ray

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.2521

zbMATH Keywords

kernelization lower boundsparameterized complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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$. A simple polynomial-time reduction reduces any input to one with at most $k^2$ points. We show that this is essentially tight under standard assumptions. More precisely, unless the polynomial hierarchy collapses to its third level, there is no polynomial-time algorithm that reduces every instance $(P,k)$ of PLC to an equivalent instance with $O(k^{2-epsilon})$ points, for any $epsilon>0$. This answers, in the negative, an open problem posed by Lokshtanov (PhD Thesis, 2009). Our proof uses 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 PLC---conditionally---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 we build on work of Goodman et al. (STOC 1989) and devise an oracle communication protocol of cost $O(nlogn)$ for PLC; its main building block is a bound of $O(n^{O(n)})$ for the order types of $n$ points that are not necessarily in general position, and an explicit algorithm that enumerates all possible order types of n points. This protocol and the lower bound on total size together yield 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.

Recommendations

• Point line cover: the easy kernel is essentially tight
• Reduction rules deliver efficient FPT-algorithms for covering points with lines
• Tight kernels for covering and hitting: point hyperplane cover and polynomial point hitting set
• Kernelization lower bounds through colors and IDs
• STACS 2005

Cited in

(17)

• Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
• Rainbow polygons for colored point sets in the plane
• Optimal data reduction for graph coloring using low-degree polynomials
• On fair covering and hitting problems
• Finding points in general position
• Computing kernels in parallel: lower and upper bounds
• Best-case and worst-case sparsifiability of Boolean CSPs
• Kernelization of the subset general position problem in geometry
• Point line cover: the easy kernel is essentially tight
• Reduction rules deliver efficient FPT-algorithms for covering points with lines
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Parameterized complexity of geometric covering problems having conflicts
• Geometric covering number: covering points with curves
• Nearly time-optimal kernelization algorithms for the line-cover problem with big data
• Parameterized and approximation algorithms for coverings points with segments in the plane
• Tight (double) exponential bounds for identification problems: locating-dominating set and test cover
• Best-case and worst-case sparsifiability of Boolean CSPs

This page was built for publication: Point line cover: the easy kernel is essentially tight

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962617)