Abstract: In the Hitting Set problem, one is given a collection of sets and has to find a minimum-cardinality set intersecting all sets in the input collection. In applications with noisy data (like feature selection, genome-wide association studies, and optimal medication), one is rather interested in Multiple Hitting Set, where the solution has to intersect each input set a given number of times. In 1998, Weihe presented a data reduction algorithm for Hitting Set that turned out effective in practise. We observe that Weihe's algorithm actually computes linear-size problem kernels for Hitting Set parameterized by the Dilworth number of the incidence graph and thus initiate parameterized complexity studies with respect to the Dilworth number: it was introduced by Foldes and Hammer in 1978 and is bounded from above by the neighborhood diversity, which is frequently studied in the context of parameterized complexity theory. We generalize Weihe's kernelization to Multiple Hitting Set and speed it up using matrix multiplication, allowing for sequentual subquadratic-time implementations and parallel implementations using NC1 circuits. We experimentally compare the data reduction effect of our kernelization and additional data reduction rules for Multiple Hitting Set to those derived by Moscato et al. in the context of feature selection and cancer medication applications.

Cite: van Bevern R. , Kirilin A. , Smirnov P. , Skachkov D. , Tsidulko O.
Fast and parallel kernelization of Multiple Hitting Set parameterized by Dilworth number
Mathematical optimization theory and operations research (MOTOR-2021) 05-10 Jul 2021