Kernels for Below-Upper-Bound Parameterizations of the Hitting Set and Directed Dominating Set Problems

Gregory Gutin, Mark Jones, Anders Yeo

In the {\sc Hitting Set} problem, we are given a collection $\mathcal{F}$ of subsets of a ground set $V$ and an integer $p$, and asked whether $V$ has a $p$-element subset that intersec…