Point Line Cover: The Easy Kernel is Essentially Tight

Stefan Kratsch, Geevarghese Philip, Saurabh Ray

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…