hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
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(n\log n)$
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.
