Tight Kernels for Covering and Hitting: Point Hyperplane Cover and Polynomial Point Hitting Set

International audience; The Point Hyperplane Cover problem in R d takes as input a set of n points in R d and a positive integer k. The objective is to cover all the given points with a set of at most k hyperplanes. The D-Polynomial Points Hitting Set (D-Polynomial Points HS) problem in R d takes as input a family F of D-degree polynomials from a vector space R in R d , and determines whether there is a set of at most k points in R d that hit all the polynomials in F. For both problems, we exhibit tight kernels where k is the parameter.