Optimal-size problem kernels for $d$-Hitting Set in linear time and space

René van Bevern, Pavel V. Smirnov

The known linear-time kernelizations for $d$-Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting ri…