(Non-)existence of Polynomial Kernels for the Test Cover Problem

G. Gutin, G. Muciaccia, A. Yeo

The input of the Test Cover problem consists of a set $V$ of vertices, and a collection $\mathcal{E}=\{E_1,...,E_m\}$ of distinct subsets of $V$, called tests. A test $E_q$ separates…