Line Cover and Related Problems

Matthias Bentert, Fedor v. Fomin, Petr A. Golovach +4

We study extensions of the classic \emph{Line Cover} problem, which asks whether a set of $n$ points in the plane can be covered using $k$ lines. Line Cover is known to be NP-hard,…