Abstract: The NP-hard Multiple Hitting Set problem is the problem of 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 feasibility of realizing kernelization algorithms on SIMD (Single Instruction, Multiple Data) architectures.

Cite: van Bevern R. , Kirilin A.M. , Skachkov D.A. , Smirnov P.V. , Tsidulko O.Y.
Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU
Journal of Computer and System Sciences. 2024. V.139. 103479 :1-18. DOI: 10.1016/j.jcss.2023.103479 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Sep 17, 2021
Accepted:	Aug 23, 2023
Published online:	Sep 12, 2023
Published print:	Feb 15, 2024

Identifiers:

Web of science:	WOS:001086672700001
Scopus:	2-s2.0-85172014632
Elibrary:	64856247
OpenAlex:	W3199867152

Citing: Пока нет цитирований

Altmetrics: