A Near-Linear Element Kernel for $d$-Hitting Set

In $d$-$\text{textsc}HittingSet$, the input consists of a finite universe $U$, a family $\mathcal{S}$ of subsets of $U$ with size at most $d$, and an integer $k$. The task is to decide whether at most $k$ elements of $U$ can intersect every set in $\mathcal{S}$. For every fixed $d\ge 3$, we give a one-sided randomized kernel with $O(k{\log }^{3}k)$ elements and a deterministic kernel with $O(k^2\log k)$ elements for $d$-$\text{textsc}HittingSet$. In the one-sided randomized kernel, every NO-instance is always mapped to a NO-instance, and a YES-instance is mapped to a YES-instance with constant probability. The previously known kernels for $d$-$\text{textsc}HittingSet$ contain $O(k^{d-1})$ elements and $O(k^d)$ sets. It has been asked in the literature whether $d$-$\text{textsc}HittingSet$ allows kernels with $O(k^{d-1-\epsilon })$ elements for some constant $\epsilon >0$. In this paper, we answer this question affirmatively by giving near-linear element-kernels through a re-encoding of the instance. On the other hand, our kernel may still contain $k^{O(d)}$ sets and the parameter $k$ may grow polynomially.