A kernelization algorithm for d-Hitting Set
For a given parameterized problem, pi, a kernelization algorithm is a polynomial-time pre-processing procedure that transforms an arbitrary instance of pi into an equivalent one whose size depends only on the input parameter(s). The resulting instance is called a problem kernel. In this paper, a kernelization algorithm for the 3-Hitting Set problem is presented along with a general kernelization for d-Hitting Set. For 3-Hitting Set, an arbitrary instance is reduced into an equivalent one that contains at most 5k(2) + k elements. This kernelization is an improvement over previously known methods that guarantee cubic-order kernels. Our method is used also to obtain quadratic kernels for several other problems. For a constant d >= 3, a kernelization of d-Hitting Set is achieved by a non-trivial generalization of the 3-Hitting Set method, and guarantees a kernel whose order does not exceed (2d - 1)k(d-1) + k. (C) 2009 Elsevier Inc. All rights reserved.
kernelization fixed-parameter algorithms hitting set crown decomposition vertex cover hypergraphs