zbMATH — the first resource for mathematics

Smaller kernels for hitting set problems of constant arity. (English) Zbl 1104.68519
Downey, Rod (ed.) et al., Parametrized and exact computation. First international workshop, IWPEC 2004, Bergen, Norway, September 14–17, 2004. Proceedings. Berlin: Springer (ISBN 3-540-23071-8/pbk). Lecture Notes in Computer Science 3162, 121-126 (2004).
Summary: We demonstrate a kernel of size \(O(k^{2})\) for 3-Hitting Set (Hitting Set when all subsets in the collection to be hit are of size at most three), giving a partial answer to an open question of Niedermeier by improving on the \(O (k^{3})\) kernel of Niedermeier and Rossmanith. Our technique uses the Nemhauser-Trotter linear-size kernel for Vertex Cover, and generalizes to demonstrating a kernel of size \(O (k^{r -1})\) for \(r\)-Hitting Set (for fixed \(r)\).
For the entire collection see [Zbl 1058.68004].

68Q25 Analysis of algorithms and problem complexity
68W01 General topics in the theory of algorithms
Full Text: DOI