  The NP-hard Multiple Hitting Set problem is finding a minimum-cardinality set
intersecting each of the sets in a given input collection a given number of
times. Generalizing a well-known data reduction algorithm due to Weihe, we show
a problem kernel for Multiple Hitting Set parameterized by the Dilworth number,
a graph parameter introduced by Foldes and Hammer in 1978 yet seemingly so far
unexplored in the context of parameterized complexity theory. Using matrix
multiplication, we speed up the algorithm to quadratic sequential time and
logarithmic parallel time. We experimentally evaluate our algorithms. By
implementing our algorithm on GPUs, we show the feasability of realizing
kernelization algorithms on SIMD (Single Instruction, Multiple Date)
architectures.
