Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU

René van Bevern, Artem M. Kirilin, Daniel A. Skachkov +2

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…